Inversion count in an array is a measure of how far the array is from being sorted. It is defined as the number of pairs of indices (i, j) such that i < j and array[i] > array[j]. In other words, an inversion occurs when a larger element appears before a smaller element in the array.
The Merge Sort algorithm is often used to efficiently count the number of inversions in an array. Merge Sort is a divide-and-conquer algorithm that works by recursively dividing the array into smaller subarrays, sorting them, and then merging them back together.
Here's a brief introduction to how inversion count can be calculated using the Merge Sort algorithm:
1. **Divide:** Divide the array into two halves.
2. **Conquer:** Recursively count the number of inversions in each half.
3. **Combine:** Merge the two sorted halves back together while counting the number of inversions across the two halves.
The key insight lies in the merging step. When merging two sorted halves, if an element from the right half is smaller than an element from the left half, it forms inversions with all the remaining elements in the left half. The inversion count is incremented by the number of elements remaining in the left half at that point.
Here is a Python-like pseudocode to illustrate the idea:
```python
def merge_and_count_inversions(arr, left, mid, right):
inv_count = 0
# Create temporary arrays
left_half = arr[left:mid + 1]
right_half = arr[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_half) and j < len(right_half):
if left_half[i] <= right_half[j]:
arr[k] = left_half[i]
i += 1
else:
# Inversion found
arr[k] = right_half[j]
j += 1
inv_count += (mid + 1) - (left + i)
k += 1
# Copy the remaining elements of left_half and right_half
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return inv_count
def merge_sort_and_count_inversions(arr, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
# Recursively count inversions in left and right halves
inv_count += merge_sort_and_count_inversions(arr, left, mid)
inv_count += merge_sort_and_count_inversions(arr, mid + 1, right)
# Merge the two halves and count inversions
inv_count += merge_and_count_inversions(arr, left, mid, right)
return inv_count
# Example usage
arr = [1, 20, 6, 4, 5]
result = merge_sort_and_count_inversions(arr, 0, len(arr) - 1)
print("Inversion count:", result)
```
In this pseudocode, the `merge_and_count_inversions` function is responsible for merging two sorted halves and counting inversions during the merge process. The `merge_sort_and_count_inversions` function is the recursive function that applies the divide-and-conquer strategy.
Keep in mind that this is a simplified pseudocode, and you may need to adapt it to the specific programming language you are using.
#include <stdio.h>
long long merge_and_count_inversions(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int left_half[n1], right_half[n2];
// Copy data to temporary arrays left_half[] and right_half[]
for (int i = 0; i < n1; i++)
left_half[i] = arr[left + i];
for (int j = 0; j < n2; j++)
right_half[j] = arr[mid + 1 + j];
// Merge the two halves back into the original array
int i = 0, j = 0, k = left;
long long inv_count = 0;
while (i < n1 && j < n2) {
if (left_half[i] <= right_half[j]) {
arr[k++] = left_half[i++];
} else {
// Inversion found
arr[k++] = right_half[j++];
inv_count += (mid - left + 1) - i;
}
}
// Copy the remaining elements of left_half[], if there are any
while (i < n1)
arr[k++] = left_half[i++];
// Copy the remaining elements of right_half[], if there are any
while (j < n2)
arr[k++] = right_half[j++];
return inv_count;
}
long long merge_sort_and_count_inversions(int arr[], int left, int right) {
long long inv_count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively count inversions in left and right halves
inv_count += merge_sort_and_count_inversions(arr, left, mid);
inv_count += merge_sort_and_count_inversions(arr, mid + 1, right);
// Merge the two halves and count inversions
inv_count += merge_and_count_inversions(arr, left, mid, right);
}
return inv_count;
}
int main() {
int arr[] = {1, 20, 6, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
long long result = merge_sort_and_count_inversions(arr, 0, size - 1);
printf("Inversion count: %lld\n", result);
return 0;
}
Output Snip:
Inversion count: 5
Process returned 0 (0x0) execution time : 0.075 s
Press any key to continue.
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
0 Comments