Answer the following part:
a) 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 E(X).
b) Use Example 5 in Section 3.3 to show that E(X) ≤ n(n − 1)/2.
c) Show that the sort makes at least one comparison for every inversion of two integers in the input.
d) Let I (P ) be the random variable that equals the number of inversions in the permutation P . Show that
E(X) ≥ E(I ).
e) Let I j,k be the random variable with j,k (P ) = 1 if ak precedes a j in P and I j,k = 0 otherwise. Show that
f ) Show that
g) Show that E(I j,k ) = 1/2.
h) Use parts (f) and (g) to show that E(I ) = n(n − 1)/4.
i) Conclude from parts (b), (d), and (h) that the average number of comparisons used to sort n integers is .