Counting Inversion

An inversion in an array refers to a pair of elements (a[i], a[j]) where i < j but a[i] > a[j]. The count of inversions measures how far the array is from sorted order.

Java example using merge sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int countInversions(int[] arr) {
  return countInv(arr, 0, arr.length - 1);
}

int countInv(int[] arr, int l, int r) {
  if (l >= r) return 0;

  int m = (l + r) / 2;
  int left = countInv(arr, l, m);
  int right = countInv(arr, m + 1, r);

  return left + right + mergeAndCount(arr, l, m, r);
}

int mergeAndCount(int[] arr, int l, int m, int r) {
  // MergeSort logic
  int count = 0;
  // Count inversions while merging
  return count;
}

C++ example using BST:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int countInversions(vector<int> arr) {
  set<int> s; 
  int invCount = 0;

  for(int i = arr.size() - 1; i >= 0; i--) {
    invCount += s.size();
    s.insert(arr[i]);
  }

  return invCount;
}

Python example using brute force:

1
2
3
4
5
6
7
8

def count_inversions(arr):
  count = 0
  for i in range(len(arr)):
    for j in range(i+1, len(arr)):
      if arr[i] > arr[j]:
        count += 1
  
  return count

Inversion count is useful for quantifying presortedness and analyzing sorting algorithms.

In computer science and algorithms, counting inversions is a fundamental concept often used in sorting and ranking problems. An inversion is a pair of indices ( (i, j) ) such that ( i < j ) but ( A[i] > A[j] ). Counting inversions in an array helps to quantify how far the array is from being sorted. A sorted array has zero inversions.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class CountInversions {
    public static int countInversions(int[] A) {
        int count = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j]) count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] A = {4, 3, 2, 1};
        System.out.println(countInversions(A));
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>
using namespace std;

int countInversions(int A[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (A[i] > A[j]) count++;
        }
    }
    return count;
}

int main() {
    int A[] = {4, 3, 2, 1};
    cout << countInversions(A, 4) << endl;
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def countInversions(A):
    count = 0
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] > A[j]:
                count += 1
    return count

A = [4, 3, 2, 1]
print(countInversions(A))

All the example codes above have a time complexity of ( O(n^2) ).

Q&A

What is the largest-possible number of inversions a 6-element array can have?

The largest-possible number of inversions a 6-element array can have is when the array is sorted in descending order. In this case, every pair of elements ( (i, j) ) where ( i < j ) will be an inversion.

For a 6-element array, you can calculate the largest-possible number of inversions by considering each element and how many elements are greater than it and come before it in the array.

Mathematically, for an array of ( n ) elements, the largest-possible number of inversions is ( \frac{n * (n - 1)}{2} ).

So, for a 6-element array:

[ \text{Largest-possible number of inversions} = \frac{6 * 5}{2} = 15 ]

Can we do better than the quadratic time complexity for this problem?

Yes, the problem of counting inversions can be solved more efficiently than in quadratic time. One common approach is to use a modified Merge Sort algorithm. This algorithm works in ( O(n \log n) ) time, which is more efficient than the ( O(n^2) ) time needed for a naive approach that checks every pair.

In the modified Merge Sort, while merging two sorted halves, we count the number of inversions where the first element is in the left half and the second element is in the right half. These are precisely the inversions that a regular Merge Sort would “fix” during the merge step.

By counting these inversions at each recursive merge step and summing them up, we can count all inversions in the array. This maintains the ( O(n \log n) ) time complexity of the Merge Sort algorithm.