In computer science, an inversion in an Array is a situation where a pair of elements are out of order. Specifically, for an array arr[], an inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Counting the number of inversions in an array is a common problem in various algorithms and is useful for measuring how far an array is from being sorted. Let us delve into understanding how to count inversions in an array efficiently using different approaches, starting with the brute-force method and progressing to the optimized divide-and-conquer technique.
1. What Is an Inversion in an Array?
An inversion in an array is a pair of elements such that the order of their indices contradicts the order of their values. Specifically, in an array arr, an inversion is a pair of indices (i, j) such that:
i < jarr[i] > arr[j]
Inversions measure how “far” an array is from being sorted. For example:
Input Array: [8, 4, 2, 1] Inversions: (8, 4), (8, 2), (8, 1), (4, 2), (4, 1), (2, 1) Total Inversions: 6
2. Brute-Force Approach?
The brute-force approach involves comparing every pair of elements in the array to count inversions. This approach has a time complexity of O(n2).
2.1 Code Example
Let’s examine the following code.
package com.jcg.example;
import java.util.*;
public class BruteForceInversionCount {
public static int countInversions(int[] arr) {
int n = arr.length;
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;
}
public static void main(String[] args) {
int[] arr = {8, 4, 2, 1};
System.out.println("Number of inversions: " + countInversions(arr));
}
}
2.1.1 Code Example
The BruteForceInversionCount class demonstrates a brute-force approach to counting inversions in an array. The method countInversions accepts an array of integers as input and returns the total number of inversions in the array.
The method works by iterating through all possible pairs of elements in the array using nested loops. The outer loop runs from the first element to the second-to-last element, represented by the variable i. The inner loop starts from the element immediately after i, represented by the variable j, and iterates to the end of the array.
For each pair of indices i and j, the code checks if the value at index i is greater than the value at index j. If this condition is true, it indicates an inversion, and the counter count is incremented.
The method completes the iteration over all pairs, summing up the total number of inversions. Finally, the count is returned as the result.
The main method demonstrates the usage of this approach. It initializes an example array {8, 4, 2, 1}, calls the countInversions method, and prints the total number of inversions. For this input array, the output is Number of inversions: 6, as there are six pairs where a larger number precedes a smaller number.
2.1.2 Code Output
The code when executed give the following output:
Number of inversions: 6
3. Optimized Approach: Divide-And-Conquer
This approach leverages the merge-sort algorithm to count inversions efficiently with a time complexity of O(n log n).
3.1 Code Example
Let’s examine the following code.
package com.jcg.example;
import java.util.*;
public class OptimizedInversionCount {
public static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
int i = left; // Left subarray
int j = mid + 1; // Right subarray
int k = left; // Merged array
int invCount = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
invCount += (mid - i + 1); // All remaining elements in left subarray are inversions
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left; i <= right; i++) arr[i] = temp[i];
return invCount;
}
public static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
int invCount = 0;
if (left < right) {
int mid = (left + right) / 2;
invCount += mergeSortAndCount(arr, temp, left, mid);
invCount += mergeSortAndCount(arr, temp, mid + 1, right);
invCount += mergeAndCount(arr, temp, left, mid, right);
}
return invCount;
}
public static void main(String[] args) {
int[] arr = {8, 4, 2, 1};
int[] temp = new int[arr.length];
System.out.println("Number of inversions: " + mergeSortAndCount(arr, temp, 0, arr.length - 1));
}
}
3.1.1 Code Example
The OptimizedInversionCount class demonstrates a more efficient approach to counting inversions in an array using a divide-and-conquer technique. The method mergeSortAndCount utilizes the merge sort algorithm to divide the array into subarrays and count the inversions during the merging process.
The mergeSortAndCount method is a recursive function that divides the input array into two halves, calls itself to sort and count inversions in each half, and then merges the two sorted halves while counting inversions that occur across the two halves. The recursion continues until the array is reduced to individual elements, which are inherently sorted.
The mergeAndCount method is responsible for merging two sorted subarrays and counting the inversions that occur during the merge. The subarrays are defined by the indices left, mid, and right. The method uses two pointers, i for the left subarray and j for the right subarray, and a third pointer, k, for the merged array.
During the merging process, if the element at index i is less than or equal to the element at index j, it is copied to the merged array. However, if the element at index i is greater than the element at index j, it indicates that all remaining elements in the left subarray (from index i to mid) form inversions with the current element in the right subarray. The inversion count is updated accordingly.
After the merging process, any remaining elements from the left or right subarray are copied into the merged array, and the merged array is copied back to the original array. The inversion count is then returned.
The main method initializes an example array {8, 4, 2, 1} and a temporary array temp used during the merging process. The mergeSortAndCount method is called, and the total number of inversions is printed. For this input array, the output is Number of inversions: 6, as there are six pairs where a larger number precedes a smaller number.
3.1.2 Code Output
The code when executed give the following output:
Number of inversions: 6
4. Comparison
| Approach | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|
| Brute-Force | O(n2) | O(1) | Simple to implement | Inefficient for large arrays |
| Divide-And-Conquer | O(n log n) | O(n) | Efficient for large arrays, scales well | Requires additional space for temporary arrays |
5. Conclusion
Counting inversions in an array can be achieved using either a brute-force or an optimized approach. The brute-force method is straightforward but inefficient for large arrays, while the divide-and-conquer method is highly efficient and scales well. Use the optimized approach when dealing with large datasets to achieve better performance.
