Inversion Count
The inversion count concept is used in the array. An inversion counts measures how far an array is from being sorted. To count the number of inversions in an array, find pairs of elements where the left index i is less than the right index j, but the left value arr[i] is greater than arr[j].
- If an array is already sorted, the total inversion count is 0.
- But if an array is sorted in descending order, then the total inversion count is maximum because we will be able to get the maximum couple of elements which is present in the array.
- For identifying the correct pairs, we traverse the array, and find the element present at ith index and compare it with (i + 1)th index;if it is greater than the next index, then we will form the pair of it and increase the number of inversions count by one.
- In this way, we traverse over the array starting from the 0thindex towards the (n-1)th index and increase the value of the inversion count if we find the correct pairs according to the above-specified condition.
Example: Inversion Count
Example 1:
Input: A = {10, 1, 2, 4, 13, 9, 5}
Output: Total count of inversions is: 8
Explanation: The number of possible inversions is: {(10, 1), (10, 2), (10, 4), (10, 9), (10, 5, (13, 9), (13, 5), (9, 5)}
Example 2:
Input: A = {1, 5, 2, 4, 13, 19, 15}
Output: Total count of inversions is: 3
Explanation: The number of possible inversions is: {(5, 2), (5, 4), (19, 15)}
Example 3:
Input: A = {7, 5, 12, 4, 1, 9, 15, 3, 8}
Output: Total count of inversions is: 16
Explanation: The number of possible inversions is: {(7, 5), (7, 4), (7, 1), (7, 3), (5, 4), (5, 1), (5, 3), (12, 4), (12, 1), (12, 9), (12, 3), (12, 8), (4, 1), (4, 3), (15, 3), (15, 8)}.
Approaches to Solve Inversion Count Problem
There are the following two approaches to solve the problem:
- Brute Force Approach
- Using Merge Sort
Brute Force Approach
In this approach, we traverse the array from start to the end and compare the elements of the right-side element with every other element. If the current element is greater than the other element increases the count of inversions. Continue this process until we check the last element of the given array. Finally, we print the total number of inversions by using the nested loop.
Algorithm
Step 1: Take an array of 'n' non-negative integers from the user in the main function.
Step 2: Create a function named inversion() that accepts the array and its size as arguments. This function uses the Merge Sort technique to count inversions and returns the total inversion count.
Step 3: Recursively divide the array into two halves until each subarray contains a single element. While merging the sorted halves, compare the elements. If the left element is greater than the right element, increment the inversion count by (mid − i + 1) and continue merging.
Step 4: After all recursive calls and merging are completed, return the total inversion count to the main function and print the result.
Implementation of Naïve Approach for Inversion Count in Python/ Java/ C/ C++/ C#
Python
# Function to count the total number of inversions
def Inversion(arr, n):
ic = 0
# Compare each element with the remaining elements
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
ic += 1
return ic
# Static array values
A = [8, 4, 2, 1]
n = len(A)
# Find inversion count
count = Inversion(A, n)
print("Array:", end=" ")
for i in A:
print(i, end=" ")
print("\nTotal number of inversions:", count)
Java
public class Main {
// Function to count the total number of inversions
static int Inversion(int arr[], int n) {
int ic = 0;
// Compare each element with the remaining elements
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
ic++;
}
}
}
return ic;
}
public static void main(String[] args) {
// Static array values
int[] A = {8, 4, 2, 1};
int n = A.length;
// Find inversion count
int count = Inversion(A, n);
System.out.print("Array: ");
for (int i = 0; i < n; i++) {
System.out.print(A[i] + " ");
}
System.out.println("\nTotal number of inversions: " + count);
}
}
C
#include// Function to count the total number of inversions int Inversion(int arr[], int n) { int ic = 0, i, j; // Compare each element with the remaining elements for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { ic++; } } } return ic; } int main() { // Static array values int array[] = {8, 4, 2, 1}; int n = sizeof(array) / sizeof(array[0]); // Find inversion count int count = Inversion(array, n); printf("Array: "); for (int i = 0; i < n; i++) { printf("%d ", array[i]); } printf("\nTotal number of inversions: %d\n", count); return 0; }
C++
#includeusing namespace std; // Function to count the total number of inversions int Inversion(int arr[], int n) { int ic = 0; // Compare each element with the remaining elements for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { ic++; } } } return ic; } int main() { // Static array values int array[] = {8, 4, 2, 1}; int n = sizeof(array) / sizeof(array[0]); // Find inversion count int count = Inversion(array, n); cout << "Array: "; for (int i = 0; i < n; i++) { cout << array[i] << " "; } cout << "\nTotal number of inversions: " << count << endl; return 0; }
C#
using System;
class Main {
// Static array values
static int[] arr = { 8, 4, 2, 1 };
// Function to count the total number of inversions
static int Inversion(int n) {
int ic = 0;
// Compare each element with the remaining elements
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
ic++;
}
}
}
return ic;
}
public static void Main() {
// Find inversion count
int count = Inversion(arr.Length);
Console.Write("Array: ");
foreach (int item in arr) {
Console.Write(item + " ");
}
Console.WriteLine("\nTotal number of inversions: " + count);
}
}
Output:
Array: 8 4 2 1 Total number of inversions: 6
Complexity Analysis
The time complexity of the above code is O (N2), as we do the asymptotically rough idea that we require n2 time to solve the problem of ' N ' elements. The space complexity of the above code is O(1).
Using the Merge Sort
In this approach, break the array into multiple subarrays until we reach the base case, then we apply the merge concept for combining the arrays by comparing the values of right subarray with the left subarray and finally merged them.
We do the partition of an array same as in merge sort until we get the single-sized subarray, at last merge them. In merging, we count the total number of inversions present in the left side and similarly in the right side and maintain the count and combine in the original order and can easily count the total number of inversions possible at last. By using this approach, we can reduce the time complexity as compared to the above method.
Algorithm
Step 1: Take an array of 'n' non-negative integers in the main function.
Step 2: Create three functions: MS(), merge_sort(), and merge(). Call MS() from the main function by passing the array and its size.
Step 3: In MS(), create a temporary array of size n and call merge_sort(arr, temp, 0, n-1). Return the inversion count obtained.
Step 4: In merge_sort(), recursively divide the array into left and right halves until each subarray contains one element. Store the inversion counts returned from both recursive calls.
Step 5: Call the merge() function to merge the two sorted subarrays. While merging, if arr[i] > arr[j], increase the inversion count by (mid - i), since all remaining elements in the left subarray are also greater than arr[j].
Step 6: Return the total inversion count from merge_sort() to MS(), and finally to the main function. Print the total number of inversions.
Implementation of Merge Sort Approach for Inversion Count in Python/ Java/ C/ C++/ C#
Python
# Function to count inversions using Merge Sort
def MS(arr, n):
temp = [0] * n
return merge_sort(arr, temp, 0, n - 1)
# Merge Sort function
def merge_sort(arr, temp, l, r):
ic = 0
if l < r:
mid = (l + r) // 2
ic += merge_sort(arr, temp, l, mid)
ic += merge_sort(arr, temp, mid + 1, r)
# Merge two sorted halves
ic += merge(arr, temp, l, mid, r)
return ic
# Merge two sorted subarrays and count inversions
def merge(arr, temp, l, mid, r):
i = l
j = mid + 1
k = l
ic = 0
while i <= mid and j <= r:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
ic += (mid - i + 1)
j += 1
k += 1
while i <= mid:
temp[k] = arr[i]
i += 1
k += 1
while j <= r:
temp[k] = arr[j]
j += 1
k += 1
for x in range(l, r + 1):
arr[x] = temp[x]
return ic
# Static array values
arr = [8, 4, 2, 1]
n = len(arr)
# Find inversion count
result = MS(arr, n)
print("Array:", end=" ")
for i in arr:
print(i, end=" ")
print("\nTotal number of inversions:", result)
Java
import java.util.Arrays;
public class Main {
// Merge two sorted subarrays and count inversions
private static int merge(int[] arr, int l, int m, int r) {
int[] left = Arrays.copyOfRange(arr, l, m + 1);
int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
int i = 0, j = 0, k = l;
int count = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
count += (m + 1) - (l + i);
}
}
while (i < left.length)
arr[k++] = left[i++];
while (j < right.length)
arr[k++] = right[j++];
return count;
}
// Merge Sort function
private static int merge_sort(int[] arr, int l, int r) {
int count = 0;
if (l < r) {
int m = (l + r) / 2;
count += merge_sort(arr, l, m);
count += merge_sort(arr, m + 1, r);
// Merge two sorted halves
count += merge(arr, l, m, r);
}
return count;
}
public static void main(String[] args) {
// Static array values
int[] A = {8, 4, 2, 1};
// Find inversion count
int count = merge_sort(A, 0, A.length - 1);
System.out.print("Array: ");
for (int num : new int[]{8, 4, 2, 1}) {
System.out.print(num + " ");
}
System.out.println("\nTotal number of inversions: " + count);
}
}
C
#include#include // Function declarations int merge_sort(int arr[], int temp[], int l, int r); int merge(int arr[], int temp[], int l, int mid, int r); // Function to count inversions int MS(int arr[], int size) { int *temp = (int *)malloc(sizeof(int) * size); int count = merge_sort(arr, temp, 0, size - 1); free(temp); return count; } // Merge Sort function int merge_sort(int arr[], int temp[], int l, int r) { int mid, ic = 0; if (r > l) { mid = (l + r) / 2; ic += merge_sort(arr, temp, l, mid); ic += merge_sort(arr, temp, mid + 1, r); // Merge two sorted halves ic += merge(arr, temp, l, mid + 1, r); } return ic; } // Merge two sorted subarrays and count inversions int merge(int arr[], int temp[], int l, int mid, int r) { int i = l, j = mid, k = l; int ic = 0; while (i <= mid - 1 && j <= r) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; ic += (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (i = l; i <= r; i++) arr[i] = temp[i]; return ic; } int main() { // Static array values int array[] = {8, 4, 2, 1}; int n = sizeof(array) / sizeof(array[0]); // Find inversion count int count = MS(array, n); printf("Array: "); for (int i = 0; i < n; i++) { printf("%d ", array[i]); printf("\nTotal number of inversions: %d\n", count); return 0; }
C++
#include#include using namespace std; // Function declarations int merge_sort(int arr[], int temp[], int l, int r); int merge(int arr[], int temp[], int l, int mid, int r); // Function to count inversions int MS(int arr[], int size) { int *temp = (int *)malloc(sizeof(int) * size); int count = merge_sort(arr, temp, 0, size - 1); free(temp); return count; } // Merge Sort function int merge_sort(int arr[], int temp[], int l, int r) { int mid, ic = 0; if (r > l) { mid = (l + r) / 2; ic += merge_sort(arr, temp, l, mid); ic += merge_sort(arr, temp, mid + 1, r); // Merge two sorted halves ic += merge(arr, temp, l, mid + 1, r); } return ic; } // Merge two sorted subarrays and count inversions int merge(int arr[], int temp[], int l, int mid, int r) { int i = l, j = mid, k = l; int ic = 0; while (i <= mid - 1 && j <= r) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; ic += (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (i = l; i <= r; i++) arr[i] = temp[i]; return ic; } int main() { // Static array values int array[] = {8, 4, 2, 1}; int n = sizeof(array) / sizeof(array[0]); // Find inversion count int count = MS(array, n); cout << "Array: "; for (int i = 0; i < n; i++) { cout << array[i] << " "; } cout << "\nTotal number of inversions: " << count << endl; return 0; }
C#
using System;
public class Program {
// Function to count inversions
static int MS(int[] arr, int n) {
int[] temp = new int[n];
return merge_sort(arr, temp, 0, n - 1);
}
// Merge Sort function
static int merge_sort(int[] arr, int[] temp, int l, int r) {
int mid, ic = 0;
if (r > l) {
mid = (l + r) / 2;
ic += merge_sort(arr, temp, l, mid);
ic += merge_sort(arr, temp, mid + 1, r);
// Merge two sorted halves
ic += merge(arr, temp, l, mid + 1, r);
}
return ic;
}
// Merge two sorted subarrays and count inversions
static int merge(int[] arr, int[] temp, int l, int mid, int r) {
int i = l, j = mid, k = l;
int ic = 0;
while (i <= mid - 1 && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
ic += (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= r)
temp[k++] = arr[j++];
for (i = l; i <= r; i++)
arr[i] = temp[i];
return ic;
}
public static void Main() {
// Static array values
int[] arr = { 8, 4, 2, 1 };
// Find inversion count
int count = MS(arr, arr.Length);
Console.Write("Array: ");
foreach (int item in arr) {
Console.Write(item + " ");
}
Console.WriteLine("\nTotal number of inversions: " + count);
}
}
Output:
Array: 1 2 4 8 Total number of inversions: 6
Complexity Analysis
The time complexity of the above code is O(N*log(N)) where ' N ' represents the number of elements. The space complexity of the above code is O(N).
Subscribe to Tpoint Tech
We request you to subscribe our newsletter for upcoming updates.
We deliver comprehensive tutorials, interview question-answers, MCQs, study materials on leading programming languages and web technologies like Data Science, MEAN/MERN full stack development, Python, Java, C++, C, HTML, React, Angular, PHP and much more to support your learning and career growth.
Contact info
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Follow us
