Compute Inversions of an Array in Θ(nlgn)

Contents
[隐藏]

1.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.)

2.Psuedocode

3.Use Java to implement this algorithm

4.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

5.Illustration

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

分享到:

One thought on “Compute Inversions of an Array in Θ(nlgn)

发表评论