Jun 132012
 

Write a function which will accept an array and count the number of inversions in the array.

Inversions in an Array are a measure of how far an array is sorted. Two elements in an array (say arr[i] and arr[j]) are said to be forming inversion iff,

arr[i] > arr[j]  AND  i < j

If an Array is already sorted, then the number of inversions will be Zero. If the array is sorted in reverse order then the number of inversions will be maximum.

For example: If array is, as given below:

8, 12, 3, 10, 15

Then Inversions will be

(8, 3), (12, 3), (12, 10)

Note: In the above example, we have considered sorting to be in ascending order. If we are talking about the descending order, then the conditions will get reversed (arr[i]j)

Solution:

Method-1: O(n2)

For each element in the array count the number of elements on the right side which are greater than the number.

This will require two nested for loops and hence O(n^2) time will be taken

    int getInvCount(int arr[], int n)
    {
        int count = 0;
        int i, j;

        for(i=0; i<n-1; i++)
            for(j=i+1; j<n; j++)
                if(arr[i] > arr[j])
                    count++;

        return count;
    }

Method-2: O(n.lg(n))

This method uses the merge sort algorithm and put the count of inversions logic in between the Merge-Sort.

In a typical Merge-Sort cycle, we have the left and right half of the array sorted and then we merge the two halves to sort the entire array. In this code we not only sort the array but also keep a count on the number of times an element from the 2nd half is put before an element of first half.

If the two halves are A and B, and we are merging them in C, then,

If element from A is moved to C, don’t increment the count

Else, If element from B is moved to C, increment the count by the number of elements remaining in A.

A good explanation of this approach can be found here…

References:

http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm
http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)