演算法 Inversions

Question

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 inversion of A.

a. List the five inversions of the array <2,3,8,6,1>

b.What array with elements from the set {1,2,..n} has the most

inversions? How many does it have?

c.What is the relationship between the running time of insertion sort

and the number of inversions in the input array? Justify your answer

Leslie · Accepted Answer

a.

(2,1), (3,1), (8,6), (8,1), (6,1)

b.

(1) The array <n, n-1, ..., 2, 1>

(2) (n-1)+(n-2)+...+1 = (n-1)n/2

c.

The number of inversions m is

the number of data movements (swappings)

needed for insertion sort.

By the way, the number of comparisons needed is at most m+(n-1),

where n is the array size (input size).

For example, the array in Part a: <2,3,8,6,1>

(to be sorted in non-decreasing order) becomes

<2,3,8,6,1> (after one comparison of 3 with 2), then

<2,3,8,6,1> (after one comparison of 8 with 3), then

<2,3,6,8,1> (after two comparisons of 6 with 8 and 3; one swap), then

<1,2,3,6,8> (after four comparisons of 1 with 8,6,3,2; four swaps).

The number of swappings of two neighbors is 5, which is actually the

number of inversions we have in Part a.