Number of inversions in an Array.

Write a function that accepts an array and counts the number of inversions in the array.

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

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

If an Array is already sorted, then the number of inversions are Zero. If the array is sorted in reverse order, then the number of inversions will be maximum. For example: If the 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 that 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