演算法 Inversions
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
1 Answer
- LeslieLv 71 decade agoFavorite 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.
Source(s): Data Structures and/or Algorithms TextbooksLogin to reply the answers