Algorithms
Count Inversions – Count Smaller on Right
Given an integer array, count the number of inversions.
Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
In other words, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
For example, given [2, 5, 4, 6, 0], return 3 since there are four inversions, (2, 0), (5, 4), (5, 0),(4, 0) and (6, 0).
An observation is that if we split the array into two halves such that both halves are sorted in increasing order then inversion count of each partition is 0. However, there might be cross inversion across the partitions. For example , Left=[2,5] and Right=[0,4,6]. Then we can see that there are 3 cross inversions (2,0), (5,0), and (5,4). But computing such cross inversion in pairwise manner would take O(n^2) and certainly not worthy.
But if we closely look then we will observe another important fact that if Left[i] and Right[j] are inversion i.e. Left[i] > Right[j] for p <= i <= q, q < j <= r , where q is the partition index, then all the elements in A[i..q] are indeed inversions for Right[j]. So, we effectively computed inversion of Right[j] by only comparing one element hence avoiding all pairwise comparison. We can do this left to right comparison while merging the two sorted arrays in O(n) time and accumulate inversion count.
Essentially there are three parts of this approach –
- Divide: We can keep halving the array recursively until we see one element.
- Conquer: We get each of the subproblems of one element and solve it right away because we know that number of inversions for these smallest subproblem (i.e. with only one element) is 0.
- Accumulate: Now, we accumulate results from the conquered i.e. solved subproblems. We accumulate by merging as described previously.
Overall complexity for divide is O(lgn) and we do accumulate in O(n) time totaling O(nlgn). Below is the simple implementation of this approach.
//merge two sorted array A[0..q] and A[q+1..r] and return inversion count of each position
public static int mergeWithInvCount(int A[], int p, int q, int r){
int crossInversionCount = 0;
int n = r-p+1;
int i = p;
int j = q+1;
int mid = q;
int k=0;
int merged[] = new int[n];
while(i <= mid && j <= r){
//satisfies i<j, A[i]<=A[j] -- so no inversion
if(A[i] <= A[j]){
merged[k++] = A[i++];
}
else{
//i<j, A[i]>A[j] --- inversion count for A[j]
crossInversionCount += (mid-i+1);
merged[k++] = A[j++];
}
}
//copy leftovers from the two partitions into merge
while(i <= mid){
merged[k++] = A[i++];
}
while(j <= r){
merged[k++] = A[j++];
}
//update A
System.arraycopy(merged, 0, A, p, n);
return crossInversionCount;
}
public static int mergeSortWithInvCount(int A[], int p, int r){
int inversionCount = 0;
if(A.length == 1){
return 0;
}
if(p < r){
int q = (p+r)/2;
//sort left side and count ic
inversionCount = mergeSortWithInvCount(A, p, q);
//sort right side and count ic
inversionCount += mergeSortWithInvCount(A, q+1, r);
//merge left and right and count cross ic
inversionCount += mergeWithInvCount(A, p, q, r);
}
return inversionCount;
}
Count Smaller On Right
Counting smaller on right is much easier as we just need to count how many time we are taking smaller element from right partition during partition. Once we get an element from left partition that means that smaller on right for current element is the count so far.
So, With a simple modification of the merge sort code we can calculate smaller on right similar to counting inversions we discussed earlier. The modification involves updating a rank array for the index of the array instead of modifying the array itself and counting smaller while taking element from right during merge. Overall complexity O(nlgn).
public static void mergeToCountSmallerOnRight(int A[], int rank[], int p, int q, int r, int count[]){
int n = r-p+1;
int i = p;
int j = q+1;
int mid = q;
int k=0;
int mergedRank[] = new int[n];
int smallerCount = 0;
while(i <= mid && j <= r){
//satisfies i<j, A[i]<A[j] -- so this is the end of smaller counts so far for A[i]. update smaller count.
if(A[rank[i]] < A[rank[j]]){
count[rank[i]] += smallerCount;
mergedRank[k++] = rank[i++];
}
//i<j, A[i]>=A[j] -- smaller element found for A[i], incr count
else{
smallerCount++;
mergedRank[k++] = rank[j++];
}
}
//copy leftovers from the two partitions into merge
while(i <= mid){
count[rank[i]] += r-q;
mergedRank[k++] = rank[i++];
}
while(j <= r){
mergedRank[k++] = rank[j++];
}
//update rank
System.arraycopy(mergedRank, 0, rank, p, n);
}
public static void countSmallerOnRightWithMerge(int A[], int rank[], int p, int r, int count[]){
if(A.length == 1){
return;
}
if(p < r){
int q = (p+r)/2;
//sort left side and count ic
countSmallerOnRightWithMerge(A, rank, p, q, count);
//sort right side and count ic
countSmallerOnRightWithMerge(A, rank, q+1, r, count);
//merge left and right and count cross ic
mergeToCountSmallerOnRight(A, rank, p, q, r, count);
}
}
public static int[] countSmallerOnRightWithMerge(int A[]){
int n = A.length;
int[] rank = new int[n];
int count[] = new int[n];
for(int i = 0; i < n; i++){
rank[i] = i;
}
countSmallerOnRightWithMerge(A, rank, 0, n-1, count);
return count;
}