演算法 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...

Answer 1

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.