Count inversions in an array

The task of counting inversions in an array involves determining how far the array is from being sorted. An inversion occurs when a pair of elements in the array is in the wrong order. This concept has applications in various scenarios, such as sorting algorithms and similarity calculations. In this article, we will delve into the problem of counting inversions, mentioned a detailed explanation, outline an effective approach, offer pseudocode and an algorithm, explain the output, analyze time complexity, and present concise code examples.

Problem Statement

Given an array, the goal is to count the number of inversions in the array. An inversion occurs when arr[i] > arr[j] for any i < j.

Example

Consider the array: Array: [1, -4, 7, 6, 4, 5, 8]

In this array, there are 6 inversion pairs: (-4, 7), (-4, 6), (-4, 5), (-4, 8), (7, 6), and (6, 5).

Approach to Solve the Problem

A simple approach to solve this problem involves using two nested loops. For each element arr[i], we iterate through the remaining elements to check if there is any element arr[j] (where j > i) such that arr[i] > arr[j]. If such a condition is met, we increment a counter to keep track of the inversions.

Pseudocode

count_inversions(arr, size):
    counter = 0
    for i from 0 to size - 2:
        for j from i + 1 to size - 1:
            if arr[i] > arr[j]:
                increment counter
    
    print "Array:", arr
    print "Inversions pair:", counter

Algorithm Explanation

1. Initialize a counter to keep track of the inversions.
2. Iterate through each element in the array using i.
3. For each i, iterate through the remaining elements using j.
4. Check if arr[i] is greater than arr[j].
5. If the condition is satisfied, increment the counter.
6. Print the original array and the inversion count.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//C Program 
//Count inversions in an array
#include <stdio.h>
 //print the array elements
void display(int arr[], int size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		printf("  %d", arr[i]);
	}
}
//Count all inversions pairs in given array
void count_inversions(int arr[], int size)
{
	int counter = 0;
	for (int i = 0; i < size; ++i)
	{
		for (int j = i + 1; j < size; ++j)
		{
			if (arr[i] > arr[j])
			{
				//When get a new inversions pair
				counter++;
			}
		}
	}
	printf("\n Array : ");
	display(arr, size);
	printf("\n Inversions pair : %d\n", counter);
}
int main()
{
	//Define array elements
	int arr[] = {
		1,
		-4,
		7,
		6,
		4,
		5,
		8
	};
	//Count size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	count_inversions(arr, size);
	return 0;
}

 Array :   1  -4  7  6  4  5  8
 Inversions pair : 6

// Java program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			System.out.print(" " + arr[i]);
		}
	}
	//Count all inversions pairs in given array
	public void count_inversions(int[] arr, int size)
	{
		int counter = 0;
		for (int i = 0; i < size; ++i)
		{
			for (int j = i + 1; j < size; ++j)
			{
				if (arr[i] > arr[j])
				{
					//When get a new inversions pair
					counter++;
				}
			}
		}
		System.out.print("\n Array : ");
		display(arr, size);
		System.out.print("\n Inversions pair : " + counter + "\n");
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//Define array elements
		int[] arr = {
			1,
			-4,
			7,
			6,
			4,
			5,
			8
		};
		//Count size of array
		int size = arr.length;
		obj.count_inversions(arr, size);
	}
}

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

//Include header file
#include <iostream>

using namespace std;
// C++ program 
// Count inversions in an array
class MyArray
{
	public:
		//print given array elements
		void display(int arr[], int size)
		{
			int i = 0;
			for (i = 0; i < size; i++)
			{
				cout << " " << arr[i];
			}
		}
	//Count all inversions pairs in given array
	void count_inversions(int arr[], int size)
	{
		int counter = 0;
		for (int i = 0; i < size; ++i)
		{
			for (int j = i + 1; j < size; ++j)
			{
				if (arr[i] > arr[j])
				{
					//When get a new inversions pair
					counter++;
				}
			}
		}
		cout << "\n Array : ";
		this->display(arr, size);
		cout << "\n Inversions pair : " << counter << "\n";
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr[] = {
		1 , -4 , 7 , 6 , 4 , 5 , 8
	};
	//Count size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.count_inversions(arr, size);
	return 0;
}

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

//Include namespace system
using System;
// C# program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	public void display(int[] arr, int size)
	{
		int i = 0;
		for (i = 0; i < size; i++)
		{
			Console.Write(" " + arr[i]);
		}
	}
	//Count all inversions pairs in given array
	public void count_inversions(int[] arr, int size)
	{
		int counter = 0;
		for (int i = 0; i < size; ++i)
		{
			for (int j = i + 1; j < size; ++j)
			{
				if (arr[i] > arr[j])
				{
					//When get a new inversions pair
					counter++;
				}
			}
		}
		Console.Write("\n Array : ");
		display(arr, size);
		Console.Write("\n Inversions pair : " + counter + "\n");
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr = {
			1 , -4 , 7 , 6 , 4 , 5 , 8
		};
		//Count size of array
		int size = arr.Length;
		obj.count_inversions(arr, size);
	}
}

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

<?php
// Php program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	public	function display( $arr, $size)
	{
		$i = 0;
		for ($i = 0; $i < $size; $i++)
		{
			echo " ". $arr[$i];
		}
	}
	//Count all inversions pairs in given array
	public	function count_inversions( $arr, $size)
	{
		$counter = 0;
		for ($i = 0; $i < $size; ++$i)
		{
			for ($j = $i + 1; $j < $size; ++$j)
			{
				if ($arr[$i] > $arr[$j])
				{
					//When get a new inversions pair
					$counter++;
				}
			}
		}
		echo "\n Array : ";
		$this->display($arr, $size);
		echo "\n Inversions pair : ". $counter ."\n";
	}
}

function main()
{
	$obj = new MyArray();
	//Define array elements
	$arr = array(1, -4, 7, 6, 4, 5, 8);
	//Count size of array
	$size = count($arr);
	$obj->count_inversions($arr, $size);
}
main();

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

// Node Js program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	display(arr, size)
	{
		var i = 0;
		for (i = 0; i < size; i++)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	//Count all inversions pairs in given array
	count_inversions(arr, size)
	{
		var counter = 0;
		for (var i = 0; i < size; ++i)
		{
			for (var j = i + 1; j < size; ++j)
			{
				if (arr[i] > arr[j])
				{
					//When get a new inversions pair
					counter++;
				}
			}
		}
		process.stdout.write("\n Array : ");
		this.display(arr, size);
		process.stdout.write("\n Inversions pair : " + counter + "\n");
	}
}

function main()
{
	var obj = new MyArray();
	//Define array elements
	var arr = [1, -4, 7, 6, 4, 5, 8];
	//Count size of array
	var size = arr.length;
	obj.count_inversions(arr, size);
}
main();

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

#  Python 3 program 
#  Count inversions in an array
class MyArray :
	# print given array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	# Count all inversions pairs in given array
	def count_inversions(self, arr, size) :
		counter = 0
		i = 0
		while (i < size) :
			j = i + 1
			while (j < size) :
				if (arr[i] > arr[j]) :
					# When get a new inversions pair
					counter += 1
				
				j += 1
			
			i += 1
		
		print("\n Array : ", end = "")
		self.display(arr, size)
		print("\n Inversions pair : ", counter ,"\n", end = "")
	

def main() :
	obj = MyArray()
	# Define array elements
	arr = [1, -4, 7, 6, 4, 5, 8]
	# Count size of array
	size = len(arr)
	obj.count_inversions(arr, size)

if __name__ == "__main__": main()

 Array :   1  -4  7  6  4  5  8
 Inversions pair :  6

#  Ruby program 
#  Count inversions in an array
class MyArray

	# print given array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
	end
	# Count all inversions pairs in given array
	def count_inversions(arr, size)
	
		counter = 0
		i = 0
		while (i < size)
		
			j = i + 1
			while (j < size)
			
				if (arr[i] > arr[j])
				
					# When get a new inversions pair
					counter += 1
				end
				j += 1
			end
			i += 1
		end
		print("\n Array : ")
		self.display(arr, size)
		print("\n Inversions pair : ", counter ,"\n")
	end
end
def main()

	obj = MyArray.new()
	# Define array elements
	arr = [1, -4, 7, 6, 4, 5, 8]
	# Count size of array
	size = arr.length
	obj.count_inversions(arr, size)
end
main()

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

// Scala program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	//Count all inversions pairs in given array
	def count_inversions(arr: Array[Int], size: Int): Unit = {
		var counter: Int = 0;
		var i: Int = 0;
		while (i < size)
		{
			var j: Int = i + 1;
			while (j < size)
			{
				if (arr(i) > arr(j))
				{
					//When get a new inversions pair
					counter += 1;
				}
				j += 1;
			}
			i += 1;
		}
		print("\n Array : ");
		display(arr, size);
		print("\n Inversions pair : " + counter + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//Define array elements
		var arr: Array[Int] = Array(1, -4, 7, 6, 4, 5, 8);
		//Count size of array
		var size: Int = arr.length;
		obj.count_inversions(arr, size);
	}
}

 Array :  1 -4 7 6 4 5 8
 Inversions pair : 6

// Swift program 
// Count inversions in an array
class MyArray
{
	//print given array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	//Count all inversions pairs in given array
	func count_inversions(_ arr: [Int], _ size: Int)
	{
		var counter: Int = 0;
		var i: Int = 0;
		while (i < size)
		{
			var j: Int = i + 1;
			while (j < size)
			{
				if (arr[i] > arr[j])
				{
					//When get a new inversions pair
					counter += 1;
				}
				j += 1;
			}
			i += 1;
		}
		print("\n Array : ", terminator: "");
		self.display(arr, size);
		print("\n Inversions pair : ", counter ,"\n", terminator: "");
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//Define array elements
	let arr: [Int] = [1, -4, 7, 6, 4, 5, 8];
	//Count size of array
	let size: Int = arr.count;
	obj.count_inversions(arr, size);
}
main();

 Array :   1  -4  7  6  4  5  8
 Inversions pair :  6

Time Complexity Analysis

The algorithm employs two nested loops to compare each element with the remaining elements. This results in a time complexity of O(n^2), where n is the size of the array. As a result, the algorithm becomes inefficient for larger arrays.