find number of pairs in an array that are out-of-order

Question

I have written a program that inputs an array of n elements and outputs the number of pair of elements that are out-of-order.

We will call a pair of elements arr[i] and arr[j] out-of-order if i < j and arr[i] > arr[j].

The running time of my program is O(n^2). It's a naive approach with two nested for loops. I was wondering if there is another way to solve this problem in less time. maybe in O(nLogn) time?

Answer 1

The algorithm you are looking for is called Counting inversions. Yes you can solve this problem using divide and conquer approach and the time complexity will be O(nlogn). It's similar to merge sort and additionally we need to keep track of inversions count. I am only printing the inversions count.

public class InversionsInOrderNSquared {
    public static void main(String[] args) {
        int array[] = { 10, 15, 2, 2, -4, 100, 99999, -10 };
        System.out.println("Inversions Count: "+inversions(array));
    }

    private static int inversions(int[] array) {
        int n = array.length;
        int inversionCountLeft = 0;
        int inversionCountRight = 0;
        int inversionCountCross = 0;
        if (n >= 2) {
            int mid = n / 2;
            int[] leftArray = new int[mid];
            int[] rightArray = new int[n - mid];
            for (int i = 0; i < n; i++) {
                if (i < mid) {
                    leftArray[i] = array[i];
                } else {
                    rightArray[i - mid] = array[i];
                }
            }
            inversionCountLeft = inversions(leftArray);
            inversionCountRight = inversions(rightArray);
            inversionCountCross = computeInversions(array, leftArray,
                    rightArray);
        }
        return (inversionCountLeft + inversionCountRight + inversionCountCross);
    }

    private static int computeInversions(int[] array, int[] leftArray,
            int[] rightArray) {
        int n_left = leftArray.length;
        int n_right = rightArray.length;
        int inversionCount = 0;
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < n_left && j < n_right) {
            if (leftArray[i] > rightArray[j]) {
                array[k] = rightArray[j];
                inversionCount += (n_left - i);// logic is we are doing index
                // wise element comparison
                // between 2 sorted arrays thus
                // for any index if any element
                // in left
                // sub-array is grater than
                // element in right sub array
                // that mean all the elements
                // after that element present in
                // left sub-array should be
                // grater than right sub-array
                // elements. Thus we are
                // considering (n_left - i) in
                // inversion count calculation.
                j++;

            } else {
                array[k] = leftArray[i];
                i++;
            }
            k++;
        }
        while (i < n_left) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < n_right) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
        return inversionCount;
    }
}

Execution 1:

Output:

Input array: 
int array[] = { 10, 15, 2, 2, -4, 100, 99999, -10 };
Inversions Count: 15

Execution 2:

Input array: 
int array[] = { 1,2,3,4,5,6 };

Output:
Inversions Count: 0

Regarding time complexity calculation:

computeInversions() method will take theta(n) time.

inversions() method is getting called 2 times with array size n/2. 

Hence the recurrence relation is,
T(n) = 2T(n/2) + theta(n);

It's following Master's theorem equation format.

Hence a =2, b=2 and f(n)=theta(n)

n^log a base b = n^log 2 base 2 =  n^1 = n

Thus above recurrence is matching case 2 of Master's theorem.

Thus time complexity is O(nlogn)

Answer 2

You can calculate such out of order pairs in o(nlogn) complexity.

For example if arr[] = {1,5,3,2,4} Out of order pairs are : (5,3), (5,2), (5,4), (3,2).

Below is the working code for the same :

    public static int countOutOfOrder(int []nums) {
            int len = nums.length, index=len-1, count=0, currindex=0, total=0;
            List<Integer>sorted = new ArrayList<Integer>();
            while(index>=0) {
                currindex = search(sorted, nums[index]);
                sorted.add(currindex, nums[index]);
                total+=(currindex);
                index--;
            }
            return total;
    }
        
    private static int search(List<Integer> sorted, int value) {
            int start=0, end = sorted.size()-1, mid=0;
            while(start<=end) {
                mid = (start+end)/2;
                if(sorted.get(mid) == value && (mid==start || sorted.get(mid-1) == value)) {
                    return mid;
                } else if(sorted.get(mid) <= value) {
                    start = mid+1;
                } else {
                    end = mid-1;
                }
            }
            return start;
 }

Explanation for o(nlogn) solution based on above example :

1. Maintain a list of sorted elements say sorted
2. Start from end index
   1. search in sorted list where we can insert the current element in
   2. Based on position we can insert , find total number of elements before this index that will be total inversions.
   3. Add this element in the sorted list.

Time complexity :

1. We are looping through all elements so complexity for this is o(n)
2. For each element we are searching in sorted list , search complecity is o(logn). So, total complexity is o(n)*o(logn) = o(nlogn)