In this tutorial, we will explore a C++ code for calculating inversions within an array using various techniques.
What is Inversion Count?
Inversion Count in an array signifies the distance of the array from being fully sorted. When the array is completely sorted, the inversion count is 0. Conversely, if the array is sorted in descending order, the inversion count reaches its peak.
Let us understand with an example:
Input: arr = {2, 4, 1, 3, 5}
Output: 3
There are three inversions in the array:
(2, 1), (4, 1), (4, 3)
Simple Method for Counting Inversions:
There exist various techniques for calculating inversions within an array. The primary approaches for counting inversions include:
1. Brute Force
In the Brute Force approach, each element is compared with every other element to tally the number of pairs that are arranged in reverse order.
Time Complexity: O(n^2)
Illustration with Examples:
Let's demonstrate this approach using the given instances:
Example 1:
Input: arr = {8, 4, 2, 1}
- In this example, start at 8. These are no elements to the right, so no inversions.
- Move to 4. There are two elements to the right (2 and 1) that are smaller, so there are two inversions.
- Move to 2. There is one element to the right (1) that is smaller, so one inversion.
- Move to 1. There are no elements to the right, so no inversions.
- Total inversions: 0 + 2 + 1 + 0 = 3
Example 2:
Input: arr = {3, 1, 2}
- Start at 3, there are two elements to the right (1 and 2) that are smaller, so two inversions.
- Move to 1. There is one element to the right (2) that is smaller, so one inversion.
- Move to 2. There are no elements to the right, so no inversions.
- Total inversions: 2 + 1 + 0 = 3
Algorithm:
Here is a simple approach to count inversions in an array explained in points:
- Inversions in an array indicate how far the array is from being sorted.
- An inversion is defined as a pair of elements ( arr[i], arr[j]) where i < j but arr[i] > arr[j] .
- A simple brute force approach is to compare every element with all other elements after it.
- Initialize a variable count = 0 to store the inversion count.
- Run two nested loops: the outer loop picks element arr[i], and the inner loop compares arr[i] with arr[j] where j varies from i+1 to n-1.
- If arr[i] > arr[j] , an inversion is found, so increment count by 1.
- Repeat this for each element arr[i] from 0 to n-2.
- After complete traversal, the count will store the total inversions in the array.
- The time complexity of this method is O(n^2) since nested traversal of the complete array is done.
A basic technique involves comparing each element with all subsequent elements to tally the number of inverted pairs. This quadratic method provides a fundamental understanding of how to tackle the inversion counting issue.
Program:
#include <iostream>
int countInversions(int arr[], int n) {
int count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int inversions = countInversions(arr, n);
std::cout << "Number of inversions: " << inversions << std::endl;
return 0;
}
Output:
Number of inversions: 6
2. Merge Sort Approach
Apply the merge sort algorithm to calculate the number of inversions. During the merging of two sorted halves, keep track of split inversions.
Time Complexity: O(nlogn)
Algorithm:
Here is an explanation of counting inversions using Merge Sort:
- The merge sort algorithm can be modified to count inversions while merging the sorted halves.
- The main logic is that when two sorted subarrays are merged, each element of the right subarray is compared with the elements of the left subarray.
- If an element in the right subarray is smaller than an element in the left subarray, this pair forms an inversion.
- To implement this: Divide the array into two halves using merge sort recursive logic. Count inversions in the left half and right half recursively.
- To merge the two sorted halves: Initialize indexes i, j for left and right subarrays. Initialize count variable to store split inversions.
- Compare arr[i] and arr[j] , if arr[i] > arr[j], an inversion is found.
- After that, increment count by m-i, where m is the mid index. It gives inversions between remaining unmatched left elements and arr[j].
- Increment i and j appropriately while merging.
- Return total inversions by adding left, right and split inversions.
- Overall time complexity is O(nlogn) since merge sort is used.
- Divide the array into two halves using merge sort recursive logic.
- Count inversions in the left half and right half recursively.
- Initialize indexes i, j for left and right subarrays.
- Initialize count variable to store split inversions.
Program:
#include <iostream>
#include <vector>
int mergeAndCount(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1);
std::vector<int> R(n2);
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
R[i] = arr[mid + i + 1];
}
int count = 0;
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
count += n1 - i; // Count inversions
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
return count;
}
int mergeSortAndCount(int arr[], int left, int right) {
int count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += mergeSortAndCount(arr, left, mid);
count += mergeSortAndCount(arr, mid + 1, right);
count += mergeAndCount(arr, left, mid, right);
}
return count;
}
int countInversions(int arr[], int n) {
return mergeSortAndCount(arr, 0, n - 1);
}
int main() {
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int inversions = countInversions(arr, n);
std::cout << "Number of inversions: " << inversions << std::endl;
return 0;
}
Output:
Number of inversions: 6
