Merge Sort: Counting Inversions Solution
This is one of the hard problems in the sorting section of hackerrank’s interview preparation kit problem set. Link here.
The problem asks you the following: given an array of n elementsA ={a1, a2, a3, ..., an} find how many inversions exist. An inversion occurs when two different elements ai and aj are part of the array and i < j but ai >aj . An array in increasing order has 0 inversions and an array like {2, 1, 3} has one inversion.
Solution
This problem can be solved using an enhanced version of mergesort. For an in-depth explanation read this
https://www.geeksforgeeks.org/counting-inversions/ Geeks for geeks has a much better explanation than mine. But the basic idea is that you can enhance MergeSort to count inversions. The tricky part is knowing when in MergeSort you should count the inversions. I first reviewed MergeSort and made my own implementation. Then I extended it to count inversions. You should follow the same path.
Code
long merge(vector<int>* arr, int leftBegin, int middle, int rightEnd){ int i, j, k; int n1, n2; long count =0; n1 = middle-leftBegin+1; n2 = rightEnd - middle; vector<int> leftArr (n1); vector<int> rightArr(n2); for (int i = 0; i < n1; i++)
leftArr[i]= (*arr)[i+leftBegin]; for (int j = 0; j < n2; j++)
rightArr[j]= (*arr)[j+middle+1]; i = 0; j = 0; k = leftBegin; while( i < n1 && j <n2){ if(leftArr[i] <= rightArr[j]){ (*arr)[k] = leftArr[i]; i++; }else{ (*arr)[k] = rightArr[j]; j++; count = count+ (n1-i); } k++; } while(i < n1){ (*arr)[k] = leftArr[i]; i++; k++; } while(j < n2){ (*arr)[k] = rightArr[j]; j++; k++; } return count;}long countInversions_rec(vector<int> *arr, int leftBegin, int rightEnd){ long inversions = 0; if(leftBegin >= rightEnd){ return 0; } int mid = floor( (leftBegin + rightEnd) /2 ); inversions = countInversions_rec(arr, leftBegin, mid); inversions += countInversions_rec(arr, mid+1, rightEnd); return inversions + merge(arr, leftBegin, mid, rightEnd);}long countInversions(vector<int> *arr) { int n = ( arr->size() ); return countInversions_rec(arr, 0, n-1);}
