Count Inversions in an Array

The inversion count for any array is the number of steps it will take for the array to be sorted, or how far away any array is from being sorted. If we are given an array sorted in reverse order, the inversion count will be the maximum number in that array. The inversion count for an array sorted in increasing order will be zero.

Inversion will be counted if arr[i] is greater than arr[j] where i is lesser than j.

Inversion count will be incremented in the below situation:

Example

Array: { 5, 4, 3, 2, 1} // reverse Order
Pairs: {5, 4}, {5,3, {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10

Array: {1, 2, 3, 4, 5} // increasing order
Pairs: No Pairs
Output: 0

Array: {1,5,2, 8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5

This is how pairs will be made with respect to their positions.

Naive Approach

We can check for every possible pair in an array. We will traverse the whole array and for each element, check if there exists any element which is lesser than the current element and present at the right of it. Then that pair will be counted in the inversion count.

Algorithm

arr[] --> array
invCount --> Inversion count

Step 1:
Loop x=0 to N-1 traverse whole array (last element won’t be considered no pair)

Step 2:
Inner Loop y=x+1 to N (till last element)
Case if(element at x is greater than element at y index)
Increment invCount++
and print the pair

Step 3:
Return the invCount

Complexity Analysis

Time Complexity O(N*N): Two iterations are required for array traversal.
Space Complexity O(N): O(1) No extra space used

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  static int findInversionCount(int arr[], int n) {
    int invCount = 0; //to store inversion count
    for (int ii = 0; ii < n - 1; ii++) //for each element
      for (int jj = ii + 1; jj < n; jj++) // to compare element right to current item
        if (arr[ii] > arr[jj]) {
          invCount++;
          //it will print each possible pair counted for inversion
          System.out.print("{" + arr[ii] + "," + arr[jj] + "}, ");
        }
    return invCount;
  }

  public static void main(String[] args)

  {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Size of Array:");
    int n = sc.nextInt();
    int arr[] = new int[n];

    System.out.println("Enter Array:");
    for (int x = 0; x < n; x++)
      arr[x] = sc.nextInt();
    System.out.println("\nInversion Count:" +
      findInversionCount(arr, arr.length));
  }
}

Code Snippet

Efficient Solution using Enhanced Merge Sort

In the above approach we are getting the time complexity O(N*N), but this complexity can be reduced to O(NlogN). We will divide the array into two parts and let the inversion count from the left and right parts of the array be countInv1 and countInv2, respectively. The comparisons between the elements from left and right will be counted during the merge of both arrays.

The left and right parts will look like:

Total Inversion Count: countInv1 + countInv2 + mergeArrayCountInv()

Algorithm:

arr[] --> elements will be stored
enhMergeCountInv() -->for dividing arr and merging sorted array
mergeArrayCountInv() --> for counting the inversions during merging two arrays

Step 1:
Call will be made to enhMergeCountInv() passing the arr and length of array as argument

Step 2:
Control reached to method enhMergeCountInv()
This method will divide the array into two parts and calculate the inversion count for each part separately.

left --> start index for left subarray,
right --> ending index of subarray

calculate mid for the subarray
mid=(left +right)/2

Step 3:
If left is lesser than right then count1= find inversion count for left subarray by calling enhMergeCountInv() passing arr, left, mid-1 as argument (recursive calling)

count2= find inversion count for right subarray by calling enhMergeCountInv() passing arr, mid, right (recursive calling)

count3 = mergeArrayCountInv() This method will return the inversion count during the merging of left and right subarrays.

else return countInv

Step 4:
Print inversion Count

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
import java.lang.*;

public class Solution {

  private static int enhMergeCountInv(int[] arr, int left,
    int right) {

    int countInv = 0;

    if (left < right) {
      int mid = (left + right) / 2;

      countInv += enhMergeCountInv(arr, left, mid);

      countInv += enhMergeCountInv(arr, mid + 1, right);

      countInv += mergeArrayCountInv(arr, left, mid, right);
    }

    return countInv;
  }

  //counting the inversion when merging arrays
  private static int mergeArrayCountInv(int[] arr, int ll,
    int mm, int rr) {
    int[] left = Arrays.copyOfRange(arr, ll, mm + 1);

    int[] right = Arrays.copyOfRange(arr, mm + 1, rr + 1);

    int ii = 0, jj = 0, kk = ll, swaps = 0;

    while (ii < left.length && jj < right.length) {
      if (left[ii] <= right[jj])
        arr[kk++] = left[ii++];
      else {
        arr[kk++] = right[jj++];
        swaps += (mm + 1) - (ll + ii);
      }
    }
    while (ii < left.length)
      arr[kk++] = left[ii++];
    while (jj < right.length)
      arr[kk++] = right[jj++];
    return swaps;
  }

  // Driver code
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Size of Array:");
    int n = sc.nextInt();
    int arr[] = new int[n];

    System.out.println("Enter Array:");
    for (int x = 0; x < n; x++)
      arr[x] = sc.nextInt();
    System.out.println("\nInversion Count:" +
      enhMergeCountInv(arr, 0, arr.length - 1));
  }
}

Code Snippet