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

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

int _mergeSort(int arr[], int temp[], int left, int right);

int merge(int arr[], int temp[], int left, int mid, int right);

/* This function sorts the input array and returns the number of inversions in the array */

int mergeSort(vector<int>&arr)
{   int array_size=arr.size();
   int temp[array_size];
   return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(vector<int>&arr, vector<int>&temp, int left, int right)
{
   int mid, inv_count = 0;
   if (right > left) {
       /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */
       mid = (right + left) / 2;

       /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */
       inv_count += _mergeSort(arr, temp, left, mid);
       inv_count += _mergeSort(arr, temp, mid + 1, right);

       /*Merge the two parts*/
       inv_count += merge(arr, temp, left, mid + 1, right);
   }
   return inv_count;
}

/* This funt merges two sorted arrays and returns inversion count in the arrays.*/
int merge(int arr[], int temp[], int left,
       int mid, int right)
{
   int i, j, k;
   int inv_count = 0;

   i = left; /* i is index for left subarray*/
   j = mid; /* j is index for right subarray*/
   k = left; /* k is index for resultant merged subarray*/
   while ((i <= mid - 1) && (j <= right)) {
       if (arr[i] <= arr[j]) {
           temp[k++] = arr[i++];
       }
       else {
           temp[k++] = arr[j++];

           /* this is tricky -- see above
           explanation/diagram for merge()*/
           inv_count = inv_count + (mid - i);
       }
   }

   /* Copy the remaining elements of left subarray
(if there are any) to temp*/
   while (i <= mid - 1)
       temp[k++] = arr[i++];

   /* Copy the remaining elements of right subarray
(if there are any) to temp*/
   while (j <= right)
       temp[k++] = arr[j++];

   /*Copy back the merged elements to original array*/
   for (i = left; i <= right; i++)
       arr[i] = temp[i];

   return inv_count;
}

int main()
{
   int arr[] = { 1, 20, 6, 4, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int ans = CountInv(arr);
   cout << " Number of inversions are " << ans;
   return 0;
}