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.

countInv.cpp ====== code: (EDIT ONLY THIS FILE)

/ Count inversions - homework

// Based off of mergesort

#include

#include // For copy

using namespace std;

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

// You will need this helper function that calculates the inversion while merging

// Your code here

}

int countInv(vector&nums) {

// Your code here

} // END OF COUNTINV.CPP FILE

countInv_test.cpp ===== code: (DO NOT EDIT THIS FILE)

/* 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

} / END OF COUNTINV_TEST.CPP FILE

Code an O(nlog(n)) algorithm to count the number of inversions. Hint - piggy back on the merging step of the mergesort algorithm.

Keep the COUNTINV_TEST.CPP file seperate from the COUNTINV.CPP file when coding.

Thank you so much for your help.

Answer 1

NOTE: the code written is tested via below input correctly , use indentation and copy fully to working code

trick is using merge sort merging step we have (mid-i) inversion while merging two arrays.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;

int merge(vector<int>& nums, int left, int mid, int right) {
   int i, j, k, n;
   int inv_count = 0;
   i = left, j = mid, k = left, n = nums.size();
   vector<int> temp(n);
   while ((i <= mid - 1) && (j <= right)) {
       if (nums[i] <= nums[j])
           temp[k++] = nums[i++];
       else {
           temp[k++] = nums[j++];
           // this is mid-1 inversions
           inv_count = inv_count + (mid - i);
       }
   }

   while (i <= mid - 1)
       temp[k++] = nums[i++];
   while (j <= right)
       temp[k++] = nums[j++];

   // assigned temp to nums vector
   for (i = left; i <= right; i++) {
       nums[i] = temp[i];
   }

   return inv_count;
}

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

// You will need this helper function that calculates the inversion while merging

// Your code here
   int mid, inv_count = 0;
   if (right > left) {
       mid = (right + left) / 2;
       inv_count += mergeInv(nums, left, mid);
       inv_count += mergeInv(nums, mid + 1, right);

       //merge two parts by calling helper method
       inv_count += merge(nums, left, mid + 1, right);
   }
   return inv_count;

}

int countInv(vector<int>& nums) {

// Your code here

   return mergeInv(nums, 0, nums.size() - 1);

}

int main(int argc, char const *argv[])
{
   vector<int> v = {4, 5, 6, 1, 2, 3};
   cout << countInv(v) << '\n';
   return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

OUTPUT: