Making both elements of an array zero
June 13, 2012
Recursive function to traverse linked list in reverse order
June 13, 2012

Number of inversions in an Array.

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

3 Comments

  1. Sahil says:

    Do we have any other approach ? other than merge sort?

  2. rahil says:

    ye I have same question too

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *