Given an array of numbers, how do we count the number of inversions in it?
Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] .
For example consider the array {3, 2, 1, 5, 4}
The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4.
We can always use the brute force approach of comparing all possible pairs of numbers to check if each pair is an inversion or not. This takes O(n2) time.
How do we solve this efficiently?
We can modify the merge sort procedure to count the number of inversions also!
Please check out my earlier post on Merge sort to understand how it works.
Here are the steps.
- First count the inversions in the left part
- Count the inversions in the right part
- Count the inversions if they are merged using modified merge procedure
- Adding the three counts gives the actual result
We need to change the merge procedure to count the inversions. The merge procedure works like the following.
We have two sorted arrays to merge into another array.
{1, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
- Take two pointers to start of the two arrays.
- Compare the two elements to see which element goes to the sorted list first.
- Increment the corresponding index.
- Repeat the above steps until we reach the end of either of them.
- Add the remaining elements if any.
While comparing the two elements if the left element is lesser than right element, we simply proceed.
If the right element is lesser than left elements, then it is also lesser than all elements to the right of left element. So increment the inversion counter accordingly.
For example
{…. 5, 9, 12, 15, …}
{…..3,….}
3 Appears in the right and 5 appears in left. So we can count all the inversions (5,3), (9,3), (12,3)… in this step itself.
Here is the C++ code which implements the above algorithm. The time complexity of this implementation is O(n log n).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
//This procedure is very similar to the merge procedure except it counts the inversions also | |
//arrays to be merged are arr[first:second-1] and arr[second:last] | |
int mergeAndCount(vector<int> & arr, int first, int second, int last) | |
{ | |
vector<int> temp; //temporary array to store merged elements | |
int i = first, j = second; | |
int invCount = 0; | |
while( i < second && j <= last ) | |
{ | |
//If inversion is possible | |
if( arr[i] > arr[j] ) | |
{ | |
//crucial step; understand carefully | |
//If current element in right is less than that of left, | |
//then it is also less than all the elements to the right of it hence (second-i) inversions | |
invCount += second - i; | |
temp.push_back( arr[j] ); | |
j++; | |
} | |
else | |
{ | |
temp.push_back( arr[i] ); | |
i++; | |
} | |
} | |
//Fill the temp array with left overs | |
while( i < second ) | |
{ | |
temp.push_back( arr[i++] ); | |
} | |
while ( j <= last ) | |
{ | |
temp.push_back( arr[j++] ); | |
} | |
//copy temp elements back to the original | |
copy( temp.begin(), temp.end(), arr.begin()+first); | |
return invCount; | |
} | |
//this procedure is similar to the sort procedure in merge sort | |
int sortAndCount( vector<int>& arr, int low, int high ) | |
{ | |
//If less than two elements | |
if( low >= high ) | |
return 0; | |
int mid = low + (high-low)/2; | |
int lic = sortAndCount( arr, low, mid ); | |
int ric = sortAndCount( arr, mid+1, high); | |
int ic = mergeAndCount( arr, low, mid+1, high); | |
return lic+ric+ic; | |
} | |
int getInversionCount(vector<int>& arr ) | |
{ | |
if( arr.size() > 0 ) | |
return sortAndCount( arr, 0, arr.size()-1 ); | |
return 0; | |
} | |
void Test1() | |
{ | |
//Random test case | |
int nums[] = { 3, 1, 2, 5, 4 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test2() | |
{ | |
//No inversion | |
int nums[] = { 1, 2, 3, 4, 5 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test3() | |
{ | |
//Every pair is an inversion | |
int nums[] = { 5, 4, 3, 2, 1 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test4() | |
{ | |
//Just a single element | |
int nums[] = { 1 }; | |
vector<int> arr( nums, nums+1 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test5() | |
{ | |
//one more random test case | |
int nums[] = { 2, 1, 4, 3, 6, 5 }; | |
vector<int> arr( nums, nums+6 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
int main() | |
{ | |
Test1(); | |
Test2(); | |
Test3(); | |
Test4(); | |
Test5(); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
//This procedure is very similar to the merge procedure except it counts the inversions also | |
//arrays to be merged are arr[first:second-1] and arr[second:last] | |
int mergeAndCount(vector<int> & arr, int first, int second, int last) | |
{ | |
vector<int> temp; //temporary array to store merged elements | |
int i = first, j = second; | |
int invCount = 0; | |
while( i < second && j <= last ) | |
{ | |
//If inversion is possible | |
if( arr[i] > arr[j] ) | |
{ | |
//crucial step; understand carefully | |
//If current element in right is less than that of left, | |
//then it is also less than all the elements to the right of it hence (second-i) inversions | |
invCount += second - i; | |
temp.push_back( arr[j] ); | |
j++; | |
} | |
else | |
{ | |
temp.push_back( arr[i] ); | |
i++; | |
} | |
} | |
//Fill the temp array with left overs | |
while( i < second ) | |
{ | |
temp.push_back( arr[i++] ); | |
} | |
while ( j <= last ) | |
{ | |
temp.push_back( arr[j++] ); | |
} | |
//copy temp elements back to the original | |
copy( temp.begin(), temp.end(), arr.begin()+first); | |
return invCount; | |
} | |
//this procedure is similar to the sort procedure in merge sort | |
int sortAndCount( vector<int>& arr, int low, int high ) | |
{ | |
//If less than two elements | |
if( low >= high ) | |
return 0; | |
int mid = low + (high-low)/2; | |
int lic = sortAndCount( arr, low, mid ); | |
int ric = sortAndCount( arr, mid+1, high); | |
int ic = mergeAndCount( arr, low, mid+1, high); | |
return lic+ric+ic; | |
} | |
int getInversionCount(vector<int>& arr ) | |
{ | |
if( arr.size() > 0 ) | |
return sortAndCount( arr, 0, arr.size()-1 ); | |
return 0; | |
} | |
void Test1() | |
{ | |
//Random test case | |
int nums[] = { 3, 1, 2, 5, 4 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test2() | |
{ | |
//No inversion | |
int nums[] = { 1, 2, 3, 4, 5 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test3() | |
{ | |
//Every pair is an inversion | |
int nums[] = { 5, 4, 3, 2, 1 }; | |
vector<int> arr( nums, nums+5 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test4() | |
{ | |
//Just a single element | |
int nums[] = { 1 }; | |
vector<int> arr( nums, nums+1 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
void Test5() | |
{ | |
//one more random test case | |
int nums[] = { 2, 1, 4, 3, 6, 5 }; | |
vector<int> arr( nums, nums+6 ); | |
cout << getInversionCount( arr) << endl; | |
} | |
int main() | |
{ | |
Test1(); | |
Test2(); | |
Test3(); | |
Test4(); | |
Test5(); | |
return 0; | |
} |