Chapter 7.4, Problem 41E

In this exercise we derive an estimate of the average-case complexity of the variant of the bubble sort algorithm that terminates once a pass has been made with no interchanges. Let Ibe the random variable on the set of permutations of a set ofndistinct integers {a j , a₂,..a_n} with aj< a₂< -< a_nsuch that A’(P) equals the number of comparisons used by the bubble sort to put these integers into increasing order.

1. Show that, under the assumption that the input is equally likely to be any of the n! permutations of these integers, the average number of comparisons used by the bubble sort equals £(X).

UseExample ;inSection 3.3to show that £(X)< n(n -1)/2.

Show that the sort makes at least one comparison for every inversion of two integers in the input.

LetIfP)be the random variable that equals the number of inversions in the permutationP.Show that E(I) >£(J).

Let fa be the random variable withIjjffl= 1 if precedesajinPandkf, = 0otherwise. Show thatIfP) = IjrfP).

Show thatE(I)=Ik£] ;k).

Show that E(Jj-fc) = 1/2.[Hint:Show that Etfy, fc) = probability thatttyprecedesajin a permutationP.Then show it is equally likely for

to precedeajas it is for(ijto precede nj, in a permutation.]

Use parts (f) and (g) to show that E(E) = n(n -1)/4.

Conclude from parts (b), (d), and (h) that the average number of comparisons used to sortnintegers is 0(n²).