Inversion of Array

An inversion in an array refers to a pair of elements (a[i], a[j]) where i < j but a[i] > a[j]. The number of inversions quantifies how close an array is to being fully sorted.

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 mergeSortAndCount(arr, 0, arr.length - 1);
}

int mergeSortAndCount(int[] arr, int lo, int hi) {
  if (lo >= hi) return 0;

  int mid = lo + (hi - lo) / 2;
  int leftInv = mergeSortAndCount(arr, lo, mid);
  int rightInv = mergeSortAndCount(arr, mid+1, hi);

  int splitInv = mergeAndCount(arr, lo, mid, hi);

  return leftInv + rightInv + splitInv;
}

int mergeAndCount(int[] arr, int lo, int mid, int hi) {
  // Merge logic + count split inversions 
  return splitInv;
}

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 += distance(s.begin(), s.lower_bound(arr[i]));
    s.insert(arr[i]);
  }
  
  return invCount;
}

Python example using brute force:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Inversion count quantifies presortedness and aids in analyzing sorting algorithms.

Here are some ways to visualize and think about inversions in arrays:

• Graphical plot: Plot the array values on a number line. Inversions visually appear as crosses on the plot.

For [3, 2, 1, 5, 4]:

3 —- \ 2 –
1

5
4

• Swap count: If you imagine bubble sort swapping adjacent inverted pairs, the number of swaps equals the inversion count.

• Order violation: An inversion violates the sorted order of elements. Visualizing how many times an element appears before a smaller value aids understanding.

• Distance from sorted: The inversion count provides a metric for how far an array is from sorted order. The higher the inversions, the more disordered the array is.

• Tree visualization: For busted algorithms like merge sort, you can visualize splits and merges of the array on a tree, counting inversions at each merge.

The main idea is to visualize inverted pairs of out-of-order elements. Graphically marking violations of sorted order provides an intuition into counting and understanding inversions. These visual metaphors can help make an abstract concept more concrete.

Inversion in an array is a pair of indices (i, j) such that i < j but array[i] > array[j]. In simpler terms, if an element at a lower index is greater than an element at a higher index, it’s considered an inversion. Inversions are a way to measure how far an array is from being sorted. A sorted array has zero inversions.

Let’s use the example array [8, 4, 2, 1] to demonstrate how the number of inversions are counted in each iteration using the simple nested loop approach. The table describes the process:

In this example, we start with an inversion count of 0 and loop through the array. At each iteration i, we check the subsequent elements j to see if they are smaller than array[i]. If they are, we increment the count of inversions. By the end of all iterations, we have counted 6 inversions in the array [8, 4, 2, 1].

Java Code

Here’s how you can count the number of inversions in Java using a simple nested loop:

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

public class Main {
    public static int countInversions(int[] array) {
        int count = 0;
        for(int i = 0; i < array.length; i++) {
            for(int j = i + 1; j < array.length; j++) {
                if(array[i] > array[j]) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] array = {8, 4, 2, 1};
        int result = countInversions(array);
        System.out.println("Number of inversions: " + result);
    }
}

C++ Code

Similarly, in C++, you can count inversions using nested loops:

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

#include <iostream>
using namespace std;

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

int main() {
    int array[] = {8, 4, 2, 1};
    int size = sizeof(array) / sizeof(array[0]);
    int result = countInversions(array, size);
    cout << "Number of inversions: " << result << endl;
    return 0;
}

Python Code

In Python, you can achieve this with:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

array = [8, 4, 2, 1]
result = count_inversions(array)
print(f"Number of inversions: {result}")

In these examples, we used a simple but inefficient method to count inversions, with a time complexity of O(n^2). More efficient algorithms, like using merge sort, can count inversions in O(n log n) time.