Question

The sequence 2, 4, 1, 3, 5 has three inversions (2,1), (4,1), (4,3). Using C++ Code an O(nlog(n)) algorithm to count the number of inversions. Use the Merge sort Algorithm, and use the template below: (Use the file below that to test)

countInv.cpp -------------------------------------------------------------------------------------------------------------------------------

#include <vector>
#include <algorithm>

using namespace std;

int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right) {

// Your code here

}

int countInv(vector<int>&nums) {
// Your code here

}

CountInv_test.cpp -------------------------------------------------------------------------------------------------------------------------

#include <iostream>
#include <vector>

using namespace std;

int countInv(vector<int>& numvec);

int main()
{
int n;
vector<int> numvec{4, 5, 6, 1, 2, 3};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 9
  
numvec = {1, 2, 3, 4, 5, 6};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 0
  
numvec = {6, 5, 4, 3, 2, 1};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 15
  
numvec = {0, 0, 0, 0, 0, 0};
n = countInv(numvec);
cout << "Number of inversions " << n << endl;; // Should be 0
}

Answer 1

I have combined both the files in one file.

Output:

Code:

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right, int l) {

    int i=0, j=0, k=l, count = 0;
    int left_size = left.size();
    while (i<left.size() && j<right.size()) {
        if (left[i] <= right[j])
            nums[k++] = left[i++];
        else {
            nums[k++] = right[j++];
            count += left_size - i; //add number of inversions(number of element in the left subarray after the ith element)
        }
    }
    return count;

}

int merge(vector<int>& nums, int l, int r)
{
    int ans = 0;
    if (l<r) {
        int m = (l + r) / 2;
        ans += merge(nums, l, m);     //count inversions in left subarray
        ans += merge(nums, m + 1, r); //count inversions in right subarray
        vector<int> left, right;
        left.assign(nums.begin()+l, nums.begin()+m+1);     //left subarray
        right.assign(nums.begin()+m+1, nums.begin()+r+1); //right subarray
        ans += mergeInv(nums, left, right, l); //merge count
    }
    return ans;
}

int countInv(vector<int>&nums) {

    int n = nums.size();
    return merge(nums, 0, n-1);

}
int main(){
    int n;
    vector<int> numvec{4, 5, 6, 1, 2, 3};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 9
    
    numvec = {1, 2, 3, 4, 5, 6};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 0
    
    numvec = {6, 5, 4, 3, 2, 1};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 15
    
    numvec = {0, 0, 0, 0, 0, 0};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl;; // Should be 0
}