I'm designing an algorithm to do the following: Given array A[1... n], for every i < j, find all inversion pairs such that A[i] > A[j]. I'm using merge sort and copying array A to array B and then comparing the two arrays, but I'm having a difficult time seeing how I can use this to find the number of inversions. Any hints or help would be greatly appreciated.
Counting inversions in an array
Viewed 180677
37 Answers
I've found it in O(n * log n) time by the following method.
- Merge sort array A and create a copy (array B)
Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.
2a. accumulate the number of inversions to counter variable num_inversions.
2b. remove A[1] from array A and also from its corresponding position in array B
- rerun from step 2 until there are no more elements in A.
Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)
1: Merge sort and copy to array B
B = (1, 2, 3, 6, 8, 9, 12, 14)
2: Take A[1] and binary search to find it in array B
A[1] = 6
B = (1, 2, 3, 6, 8, 9, 12, 14)
6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).
2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).
A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)
3: Rerun from step 2 on the new A and B arrays.
A[1] = 9
B = (1, 2, 3, 8, 9, 12, 14)
9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)
A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)
Continuing in this vein will give us the total number of inversions for array A once the loop is complete.
Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).
Thanks for your help. Writing out the sample arrays on a piece of paper really helped to visualize the problem.
I had a question similar to this for homework actually. I was restricted that it must have O(nlogn) efficiency.
I used the idea you proposed of using Mergesort, since it is already of the correct efficiency. I just inserted some code into the merging function that was basically: Whenever a number from the array on the right is being added to the output array, I add to the total number of inversions, the amount of numbers remaining in the left array.
This makes a lot of sense to me now that I've thought about it enough. Your counting how many times there is a greater number coming before any numbers.
hth.
Check this out: http://www.cs.jhu.edu/~xfliu/600.363_F03/hw_solution/solution1.pdf
I hope that it will give you the right answer.
- 2-3 Inversion part (d)
- It's running time is O(nlogn)
Most answers are based on MergeSort but it isn't the only way to solve this is in O(nlogn)
I'll discuss a few approaches.
Use a
Balanced Binary Search Tree- Augment your tree to store frequencies for duplicate elements.
- The idea is to keep counting greater nodes when the tree is traversed from root to a leaf for insertion.
Something like this.
Node *insert(Node* root, int data, int& count){
if(!root) return new Node(data);
if(root->data == data){
root->freq++;
count += getSize(root->right);
}
else if(root->data > data){
count += getSize(root->right) + root->freq;
root->left = insert(root->left, data, count);
}
else root->right = insert(root->right, data, count);
return balance(root);
}
int getCount(int *a, int n){
int c = 0;
Node *root = NULL;
for(auto i=0; i<n; i++) root = insert(root, a[i], c);
return c;
}
- Use a
Binary Indexed Tree- Create a summation BIT.
- Loop from the end and start finding the count of greater elements.
int getInversions(int[] a) {
int n = a.length, inversions = 0;
int[] bit = new int[n+1];
compress(a);
BIT b = new BIT();
for (int i=n-1; i>=0; i--) {
inversions += b.getSum(bit, a[i] - 1);
b.update(bit, n, a[i], 1);
}
return inversions;
}
- Use a
Segment Tree- Create a summation segment Tree.
- Loop from the end of the array and query between
[0, a[i]-1]and updatea[i] with 1
int getInversions(int *a, int n) {
int N = n + 1, c = 0;
compress(a, n);
int tree[N<<1] = {0};
for (int i=n-1; i>=0; i--) {
c+= query(tree, N, 0, a[i] - 1);
update(tree, N, a[i], 1);
}
return c;
}
Also, when using BIT or Segment-Tree a good idea is to do Coordinate compression
void compress(int *a, int n) {
int temp[n];
for (int i=0; i<n; i++) temp[i] = a[i];
sort(temp, temp+n);
for (int i=0; i<n; i++) a[i] = lower_bound(temp, temp+n, a[i]) - temp + 1;
}
The easy O(n^2) answer is to use nested for-loops and increment a counter for every inversion
int counter = 0;
for(int i = 0; i < n - 1; i++)
{
for(int j = i+1; j < n; j++)
{
if( A[i] > A[j] )
{
counter++;
}
}
}
return counter;
Now I suppose you want a more efficient solution, I'll think about it.
Implementation of counting inversions in an array with merge sort in Swift:
Note that the number of swaps is incremented by
nSwaps += mid + 1 - iL
(which is the relative length of the left side of the array minus the index of the current element in the left side)
... because that is the number of elements which the element in the right side of the array had to skip over (# of inversions) to become sorted.
func merge(arr: inout [Int], arr2: inout [Int], low: Int, mid: Int, high: Int) -> Int {
var nSwaps = 0;
var i = low;
var iL = low;
var iR = mid + 1;
while iL <= mid && iR <= high {
if arr2[iL] <= arr2[iR] {
arr[i] = arr2[iL]
iL += 1
i += 1
} else {
arr[i] = arr2[iR]
nSwaps += mid + 1 - iL
iR += 1
i += 1
}
}
while iL <= mid {
arr[i] = arr2[iL]
iL += 1
i += 1
}
while iR <= high {
arr[i] = arr2[iR]
iR += 1
i += 1
}
return nSwaps
}
func mergeSort(arr: inout [Int]) -> Int {
var arr2 = arr
let nSwaps = mergeSort(arr: &arr, arr2: &arr2, low: 0, high: arr.count-1)
return nSwaps
}
func mergeSort(arr: inout [Int], arr2: inout [Int], low: Int, high: Int) -> Int {
if low >= high {
return 0
}
let mid = low + ((high - low) / 2)
var nSwaps = 0;
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: low, high: mid)
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: mid+1, high: high)
nSwaps += merge(arr: &arr, arr2: &arr2, low: low, mid: mid, high: high)
return nSwaps
}
var arrayToSort: [Int] = [2, 1, 3, 1, 2]
let nSwaps = mergeSort(arr: &arrayToSort)
print(arrayToSort) // [1, 1, 2, 2, 3]
print(nSwaps) // 4
I recently had to do this in R:
inversionNumber <- function(x){
mergeSort <- function(x){
if(length(x) == 1){
inv <- 0
} else {
n <- length(x)
n1 <- ceiling(n/2)
n2 <- n-n1
y1 <- mergeSort(x[1:n1])
y2 <- mergeSort(x[n1+1:n2])
inv <- y1$inversions + y2$inversions
x1 <- y1$sortedVector
x2 <- y2$sortedVector
i1 <- 1
i2 <- 1
while(i1+i2 <= n1+n2+1){
if(i2 > n2 || i1 <= n1 && x1[i1] <= x2[i2]){
x[i1+i2-1] <- x1[i1]
i1 <- i1 + 1
} else {
inv <- inv + n1 + 1 - i1
x[i1+i2-1] <- x2[i2]
i2 <- i2 + 1
}
}
}
return (list(inversions=inv,sortedVector=x))
}
r <- mergeSort(x)
return (r$inversions)
}
C++ Θ(n lg n) Solution with the printing of pair which constitute in inversion count.
int merge(vector<int>&nums , int low , int mid , int high){
int size1 = mid - low +1;
int size2= high - mid;
vector<int>left;
vector<int>right;
for(int i = 0 ; i < size1 ; ++i){
left.push_back(nums[low+i]);
}
for(int i = 0 ; i <size2 ; ++i){
right.push_back(nums[mid+i+1]);
}
left.push_back(INT_MAX);
right.push_back(INT_MAX);
int i = 0 ;
int j = 0;
int start = low;
int inversion = 0 ;
while(i < size1 && j < size2){
if(left[i]<right[j]){
nums[start] = left[i];
start++;
i++;
}else{
for(int l = i ; l < size1; ++l){
cout<<"("<<left[l]<<","<<right[j]<<")"<<endl;
}
inversion += size1 - i;
nums[start] = right[j];
start++;
j++;
}
}
if(i == size1){
for(int c = j ; c< size2 ; ++c){
nums[start] = right[c];
start++;
}
}
if(j == size2){
for(int c = i ; c< size1 ; ++c){
nums[start] = left[c];
start++;
}
}
return inversion;
}
int inversion_count(vector<int>& nums , int low , int high){
if(high>low){
int mid = low + (high-low)/2;
int left = inversion_count(nums,low,mid);
int right = inversion_count(nums,mid+1,high);
int inversion = merge(nums,low,mid,high) + left + right;
return inversion;
}
return 0 ;
}
Solution One.Work well when there is a large amount of numbers
def countInversions(arr):
n = len(arr)
if n == 1:
return 0
n1 = n // 2
n2 = n - n1
arr1 = arr[:n1]
arr2 = arr[n1:]
# print(n1,'||',n1,'||',arr1,'||',arr2)
ans = countInversions(arr1) + countInversions(arr2)
print(ans)
i1 = 0
i2 = 0
for i in range(n):
# print(i1,n1,i2,n2)
if i1 < n1 and (i2 >= n2 or arr1[i1] <= arr2[i2]):
arr[i] = arr1[i1]
ans += i2
i1 += 1
elif i2 < n2:
arr[i] = arr2[i2]
i2 += 1
return ans
Solution Two.Simple solution.
def countInversions(arr):
count = 0
for i in range(len(arr)):
for j in range(i, len(arr)):
# print(arr[i:len(arr)])
if arr[i] > arr[j]:
print(arr[i], arr[j])
count += 1
print(count)
The number of inversions in an array is half the total distance elements must be moved in order to sort the array. Therefore, it can be computed by sorting the array, maintaining the resulting permutation p[i], and then computing the sum of abs(p[i]-i)/2. This takes O(n log n) time, which is optimal.
An alternative method is given at http://mathworld.wolfram.com/PermutationInversion.html. This method is equivalent to the sum of max(0, p[i]-i), which is equal to the sum of abs(p[i]-i])/2 since the total distance elements move left is equal to the total distance elements move to the right.
EDIT: This method is wrong (see comments), and there is unfortunately no way to fix it while preserving the character of the method.
Related