Compute Inversions of an Array in Θ(nlgn)

Description

Let A[1..n] be an array of n distinct numbers. If i < j and A[i]>A[j], then the pair (i,j) is called an inversion of A.

Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(nlgn) worst-case time. (Hint: Modify merge sort.)

Psuedocode

M.Merge-Sort(A, p, r)
    if(p < r)
        q = (p + r) / 2;   // q is a type of int
        left  = M.Merge-Sort(A, p, q)
        right = M.Merge-Sort(A, q + 1, r)
        inv   = M.Merge(A, p, q, r) + left + right
        return inv
    end if
    return 0
end M.Merge-Sort
M.Merge(A, p, q, r)
    n1 = q - p + 1   // length of left subarray
    n2 = r - q       // length of right subarray

    Let L[1..n1], R[1..n2] be a new array
    for i = 1 to n1
        L[i] = A[p + i - 1] // here i starts from 1. Whereas i starts from 0, L[i] = A[p + i]
    end for
    for i = 1 to n2
        L[i] = A[q + i]     // here i starts from 1. Whereas i starts from 0, R[i] = A[q + i + 1]
    end for

    i = 1
    j = 1
    k = p
    inv = 0
    while i != n1+1 and j != n2+1 do // here i starts from 1. Whereas i starts from 0, i != n1 and j != n2
        if L[i] <= R[j] then
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            inv = inv + n1 - i + 1 // here i starts from 1. Whereas i starts from 0, inv = inv + n1 - i
            j = j + 1
        end if
        k = k + 1
    end while

    if i == n1+1 then   // here i starts from 1. Whereas i starts from 0, i == n1
        for m=j to n2 do
            A[k] = R[m]
            k = k + 1
        end for
    else if j == n2+1 then // here i starts from 1. Whereas i starts from 0, j == n2
         for m=i to n1 do
             A[k] = L[m]
             k = k + 1
         end for
    end if

    return inv
end M.Merge

Use Java to implement this algorithm

public class Inverse {
	public int inverse(int[] A){
		return Merge_Sort(A, 0, A.length - 1);
	}
	
	private int Merge_Sort(int[] A, int p, int q){
		int left = 0;
		int right = 0;
		int inv = 0;
		if(p<q){
			int mid = (p + q) / 2;
			left = Merge_Sort(A, p, mid);
			right = Merge_Sort(A, mid+1, q);
			inv = Merge(A, p, mid, q) + left + right;			
		}
		return inv;
	}
	
	private int Merge(int[] A, int p, int q, int r){
		int n1 = q - p + 1;
		int n2 = r - q;
		int[] L = new int[n1];
		int[] R = new int[n2];
		
		for(int i=0; i<n1; i++){
			L[i] = A[p+i];
		}
		for(int i=0; i<n2; i++){
			R[i] = A[q+i+1];
		}
		
		int k = p;
		int i = 0;
		int j = 0;
		int inv = 0;
		while(i != n1 && j != n2){
			if(L[i] <= R[j]){
				A[k] = L[i];
				i++;
			}
			else{
				A[k] = R[j];
				j++;
				inv = inv + n1 - i; // key code
			}
			k++;
		}
		
		if(i == n1){
			for(int l = j; l<n2; l++, k++){
				A[k] = R[l];
			}
		}
		else{
			for(int l = i; l<n1; l++, k++){
				A[k] = L[l];
			}
		}
		return inv;
	}
}

Test for this algorithm

Inverse inv = new Inverse();Inverse inv = new Inverse();

int[] A = {5,6,9,8,7,5,65,4,5,6,48,56,46,54,35,4};

System.out.println(inv.inverse(A));

49

Illustration

Note: The number in the circle of the figure is computed by M.Merge(A, p, q, r).

2 thoughts on “Compute Inversions of an Array in Θ(nlgn)

  • 2020年4月12日 at 上午12:49
    Permalink

    We’re a group of volunteers and starting a new scheme in our community.
    Your website offered us with valuable information to work on. You have done a formidable task and our whole community might be thankful to you.

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × 1 =

11 − = 1