CODEWITHSUNDEEP
c++vectorsyntaxmergesort
Xgh05t
Xgh05t

Reputation: 240

Trouble implementing Mergesort algorithm in c++, syntax of vectors

I'm trying to implement mergesort in cpp, I'm having some trouble with the proper syntax with vectors, in particular the part inside the for loop where I'm merging the elements. Some help would be appreciated. My code so far gives the wrong output. Also, I was wondering if this code could be modified to count inversions as well, everytime I go in the else case, inversions increase but it's missing corner cases. I tried doing the v[i] = left[i1] as v.insert(v.begin() + i, left.at(i1)), which also did not work, I'm in general confused about the [] operator for vectors, how is it different than array [] operator?

#include <bits/stdc++.h>

using namespace std;

void mergeSort(vector<int>& v) {
    if(v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size()/2);  
        vector<int> right(v.begin() + v.size()/2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for(int i = 0; i < v.size(); i++) {
            if(i2 >= right.size() || (i1 < left.size() && left[i] < right[i])) {
                v[i] = left[i1]; i1++;
            } else {
                v[i] = right[i2]; i2++;
            }
        }       
    }   
}

int main() {
    vector<int> v = {22, 18, 12, -4, 58, 7, 31, 42};
    mergeSort(v);
    for(auto i = v.begin(); i != v.end(); i++) cout << *i << endl;
    return 0;
}

Upvotes: 0

Views: 78

Answers (2)

Steyrix
Steyrix

Reputation: 3226

I think your condition is wrong (you comparing elements of vectors with index i), try this (I also added check for inversions, as you asked). I just changed names of indexes from i2 and i1 to r and lrespectively.

for (int i = 0; i < v.size; i++) {
    if (r < right.size() && (right[r] <= left[l] || l >= left.size)) {
        if (right[r] < left[l]) inversions++; 
        v[i] = right[r++];  
    } else {
        v[i] = left[l++];
    }    
}

Upvotes: 1

fern17
fern17

Reputation: 487

Your condition is wrong. You need to use the i1 and i2 indexes because i quickly goes beyond the size of right (I checked this with a debugger, you should use it as well!) Here my full solution and some additional tests:

//#include <bits/stdc++.h>
#include <vector>
#include <iostream>

using namespace std;

void mergeSort(vector<int>& v) {
    if (v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size() / 2);
        vector<int> right(v.begin() + v.size() / 2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for (int i = 0; i < v.size(); i++) {
            if (i2 >= right.size() || (i1 < left.size() && left[i1] < right[i2])) {
                v[i] = left[i1]; i1++;
            }
            else {
                v[i] = right[i2]; i2++;
            }
        }
    }
}

void printVector(vector<int>& v)
{
    for (auto i = v.begin(); i != v.end(); i++) cout << *i << ' ';
    std::cout << std::endl;
}

void test(vector<int>& v)
{
    std::cout << "------\n";
    printVector(v);
    mergeSort(v);
    std::cout << "------\n";
    printVector(v);
    std::cout << "------\n";
}

int main() {
    vector<int> v1 = { 22, 18, 12, -4, 58, 7, 31, 42 };
    vector<int> v2 = { 10 };
    vector<int> v3 = { 10 , 20 };
    vector<int> v4 = { 20 , 10 };
    vector<int> v5 = { 20 , 10 , 5};
    vector<int> v6 = { 10 , 10 , 10 };
    vector<int> v7 = { 11 , 10 , 10 };
    vector<int> v8 = { };
    test(v1);
    test(v2);
    test(v3);
    test(v4);
    test(v5);
    test(v6);
    test(v7);
    test(v8);
    return 0;
}

Upvotes: 0

Related Questions