Count Inversions

Lecture 113:-Count Inversions

Counting inversions is a common problem in the field of algorithms and can be solved using various approaches. An inversion occurs in an array when two elements are out of their natural order (i.e., the order they should be in if the array were sorted in ascending order).

Here is an example array: [8, 4, 2, 1]

In this array, the inversions are:

1. (8, 4)
2. (8, 2)
3. (8, 1)
4. (4, 2)
5. (4, 1)
6. (2, 1)

Counting inversions involves determining how many such pairs exist in the given array.

One common technique to count inversions is by using the "Merge Sort" algorithm. The idea is that during the merge step of merge sort, while merging two sorted subarrays, you can count the inversions as you merge. Here's how it works:

1. Divide the array into two halves.
2. Recursively count the inversions in each half.
3. While merging the two halves back together, keep track of the number of inversions you encounter.

Here is a Python code example that implements this approach:

pythonCopy code

def merge(arr, temp, left, mid, right): inv_count = 0 i = left j = mid + 1 k = left while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] j += 1 inv_count += (mid - i + 1) k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp[i] return inv_count def merge_sort_and_count(arr, temp, left, right): inv_count = 0 if left < right: mid = (left + right) // 2 inv_count += merge_sort_and_count(arr, temp, left, mid) inv_count += merge_sort_and_count(arr, temp, mid + 1, right) inv_count += merge(arr, temp, left, mid, right) return inv_count def count_inversions(arr): n = len(arr) temp = [0] * n return merge_sort_and_count(arr, temp, 0, n - 1) # Example usage arr = [8, 4, 2, 1] inversion_count = count_inversions(arr) print("Number of inversions:", inversion_count)

The count_inversions function uses the merge sort technique to count the inversions in the given array. The merge_sort_and_count function performs the sorting and counting of inversions during the merging step.

This algorithm has a time complexity of O(n log n), where n is the number of elements in the array, and it can accurately count the number of inversions.