Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

array
inversions

How to count the number of inversions in an array

Educative Answers Team

The number of inversions in an array indicates the number of changes required in the array for it to be sorted.

Method

Given an array, if i < j and arr [i] > arr [j] then the pair (i,j) requires an inversion. All such pairs are calculated.

For each element, the naive approach would be to calculate the number of elements to its right that are less than it. The time complexity for this approach would be O(n2)O( n^2 ). However, t​he best approach would be to extend the merge sort. The illustration below shows the method used to calculate the inversions in an array using merge sort:

1 of 16

Implementation

In the code below, the tmergeSort() function is used to calculate the inversions in the array, recursively. The merge() function is used to merge the two sorted arrays.

Understanding the merge sort is highly recommended.

// Java implementation

class main { 

	// Function to count Inversions
	static int mergeSort(int arr[], int array_size) 
	{ 
		int temp[] = new int[array_size]; 
		return tmergeSort(arr, temp, 0, array_size - 1); 
	} 

	// This function uses merge sort to count inversion.
	static int tmergeSort(int arr[], int temp[], int left, int right) 
	{ 
		int mid, inv_count = 0; 
		if (right > left) { 
			// calculating the middle element
			mid = (right + left) / 2; 

			// calculating inversion count for left array
			inv_count = tmergeSort(arr, temp, left, mid); 
			//calculating inversion count for right array
			inv_count += tmergeSort(arr, temp, mid + 1, right); 

			// merging the two arrays
			inv_count += merge(arr, temp, left, mid + 1, right); 
		} 
		return inv_count; 
	} 

    // This function merges the two sorted arrays.
	static int merge(int arr[], int temp[], int left, int mid, int right) 
	{ 
		int i, j, k; 
		int inv_count = 0; 

		i = left; 
		j = mid; 
		k = left; 
		while ((i <= mid - 1) && (j <= right)) { 
			// No inversion will occur
			if (arr[i] <= arr[j]) { 
				temp[k++] = arr[i++]; 
			} 
			else { 
				// Inversion will occur
				temp[k++] = arr[j++]; 
				inv_count = inv_count + (mid - i); 
			} 
		} 

        // the remaining elements of left array are copied.
		while (i <= mid - 1) 
			temp[k++] = arr[i++]; 

	    // the remaining elements of right array are calculated.
		while (j <= right) 
			temp[k++] = arr[j++]; 

		for (i = left; i <= right; i++) 
			arr[i] = temp[i]; 

		return inv_count; 
	} 

	// Driver Function 
	public static void main(String[] args) 
	{ 
		int arr[] = new int[] { 83, 20, 9, 50, 115, 61, 17 }; 
		System.out.println("Inversions_count = " + mergeSort(arr, 7)); 
	} 
} 

RELATED TAGS

array
inversions
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring