Counting the number of inversions in a list

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(n²) 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).

	#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;
	}

view raw CountInversions.cpp hosted with

by GitHub

	#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;
	}

view raw CountInversions.cpp hosted with

by GitHub

Leave a Reply Cancel reply