Question

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

What would the complexity of a brute force approach be? Code an O(nlog(n)) algorithm to count the number of inversions. Hint - piggy back on the merging step of the mergesort algorithm.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Complete the code in the functions indicated to count inversions

// countlnv.cpp file

#include <iostream>
#include <vector>

using namespace std;

int numinv;

void mergeSort(vector<int>& numvec, int left, int right);
int merge(vector<int>& numvec , int left, int mid, int right);

int countInv(vector<int>& numvec) {
numinv = 0;
mergeSort(numvec, 0, numvec.size());
cout << "Sorted output: ";
for (auto ele : numvec)
   cout << ele << " ";
   cout << endl;
return numinv;
  
}

//Sorts the input vector and returns the number of inversions in that vector
void mergeSort(vector<int>& numvec, int left, int right){
// Your code here

}

int merge(vector<int>& numvec , int left, int mid, int right){
// Your code here

}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Use the following test code to evaluate your implementation

// countlnv_test.cpp

/* Count the number of inversions in O(n log n) time */
#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
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Thank you for your time and help!

Answer 1

#include <iostream>
#include <vector>

using namespace std;

int numinv;

void mergeSort(vector<int>& numvec, int left, int right);
int merge(vector<int>& numvec , int left, int mid, int right);

int countInv(vector<int>& numvec) {
        numinv = 0;
        mergeSort(numvec, 0, numvec.size());
        cout << "Sorted output: ";
        for (auto ele : numvec)
                cout << ele << " ";
        cout << endl;
        return numinv;
}

//Sorts the input vector and returns the number of inversions in that vector
void mergeSort(vector<int>& numvec, int left, int right){
        // no need to sort a single element.
        if(left + 1 < right) {
                int mid = (left + right) / 2;
                mergeSort(numvec, left, mid);
                mergeSort(numvec, mid, right);
                numinv += merge(numvec, left, mid, right);
        }
}

// mid is start of next array.
// right is excluded.
int merge(vector<int>& numvec , int left, int mid, int right){
        
    // Copy the vector to tmeporary vector, so that we can 
    // make the changes to the original
    vector<int> temp = numvec; 
 
    int inversionCount = 0; 
  
    int i = left;
    int j = mid;
    int k = left;
    while ((i <= mid - 1) && (j < right)) { 
        if (temp[i] <= temp[j]) { 
            numvec[k++] = temp[i++]; 
        } 
        else { 
            numvec[k++] = temp[j++];
            inversionCount += (mid - i);  // at this point, remaining elements are inverted
        }
    }
    
    // copy remaining elements from any half back to original array
    while (i <= mid - 1) {
        numvec[k++] = temp[i++]; 
    }
  
    while (j < right) {
        numvec[k++] = temp[j++]; 
    }
  
  
    return inversionCount;
}


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
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.