Counting Inversions

Posted on | Post modified | In , , ,

Problem

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example

  • The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
  • The sequence 1, 3, 5, 2, 4, 6 has three inversions (3, 2), (5, 2), (5, 4).

Algorithm

Method: Divide and Conquer

  • Divide: separate list into two halves A and B.
  • Conquer: recursively count inversions in each list.
  • Combine: count inversions (a, b) with a ∈ A and b ∈ B.
  • Return sum of three counts.

Time complexity: O(n log n)

  • The worst-case running time T(n) satisfies the recurrence:
    • T(n) = Θ(1), if n = 1
    • T(n) = T(⎡n/2⎤) + T(⎣n/2⎦) + Θ(n), otherwise
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
def sort_and_count(arr):
    if len(arr) <= 1:
        return arr, 0

    mid_idx = len(arr)//2
    left, count_left = sort_and_count(arr[:mid_idx])
    right, count_right = sort_and_count(arr[mid_idx:])
    sorted_arr, count_left_right = merge_and_count(left, right)

    return sorted_arr, count_left + count_right + count_left_right

def merge_and_count(left, right):
    i = 0
    j = 0
    count = 0
    sorted_res = []

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_res.append(left[i])
            i += 1
        else:
            sorted_res.append(right[j])
            count += len(left) - i
            j += 1

    if i < len(left):
        sorted_res += left[i:]
    if j < len(left):
        sorted_res += right[j:]

    return sorted_res, count

Reference