Consider the following algorithm, known as bubble sort, for sorting a list of n distinct

Chapter 4, Problem 50

(choose chapter or problem)

Consider the following algorithm, known as bubble sort, for sorting a list of n distinct numbers into increasing order. Initially they are in a random order, with all orders equally likely. The algorithm compares the numbers in positions 1 and 2, and swaps them if needed, then it compares the new numbers in positions 2 and 3, and swaps them if needed, etc., until it has gone through the whole list. Call this one sweep through the list. After the first sweep, the largest number is at the end, so the second sweep (if needed) only needs to work with the first n 1 positions. Similarly, the third sweep (if needed) only needs to work with the first n 2 positions, etc. Sweeps are performed until n 1 sweeps have been completed or there is a swapless sweep. For example, if the initial list is 53241 (omitting commas), then the following 4 sweeps are performed to sort the list, with a total of 10 comparisons: 53241 ! 35241 ! 32541 ! 32451 ! 3. 32415 ! 23415 ! 23415 ! 23145. 23145 ! 23145 ! 21345. 21345 ! 12345. (a) An inversion is a pair of numbers that are out of order (e.g., 12345 has no inversions, while 53241 has 8 inversions). Find the expected number of inversions in the original list. (b) Show that the expected number of comparisons is between 1 2 n 2 and n 2 . Hint: For one bound, think about how many comparisons are made if n 1 sweeps are done; for the other bound, use Part (a).