Trusted answers to developer questions

Educative Answers Team

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

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( 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:

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

Related Courses