Counting inversions in an array

Question

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.

thanks.

Answer 1

The only advice I could give to this (which looks suspiciously like a homework question ;) ) is to first do it manually with a small set of numbers (e.g. 5), and then write down the steps you took to solve the problem.

This should allow you to figure out a generic solution you can use to write the code.

Answer 2

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.

Answer 3

Hello rleonen,

My advice to you would be that copying the array would be uneccesary unless you wanted something more than just the number of inversions.

If you just want to count the number of inversions you should consider that you need to loop through the array, and you only care about pairs of array elements that are next to each other.

The first step I would take is to write the problem on paper (actually write an "array" out with some inversions in it). Then solve the problem manually. Once you've done this you should try to express your solution in pseudo code. As I said if you consider that you only care about pairs of elements that are next to each other this will help you simplify your solution.

This is one approach that I used to use when I was a programming student. Writing it on paper helps you understand the problem and solution in non programming terms first.

Good luck with your assignment. I hope I've been helpful.

Docta

Answer 4

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.

Answer 5

I've found it in O(n * log n) time by the following method.

1. Merge sort array A and create a copy (array B)

2. 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

3. 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.

Answer 6

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.

Answer 7

Use mergesort, in merge step incremeant counter if the number copied to output is from right array.

Answer 8

nice answer from el diablo but to complete it some considerations in case of element duplication have to be cared!