Counting Comparisons and Swaps

4

1. A student is using a bubble sort to rearrange seven numbers into ascending order.
   Her correct solution is as follows:

   Initial list	18	17	13	26	10	14	24
   After 1st pass	17	13	18	10	14	24	26
   After 2nd pass	13	17	10	14	18	24	26
   After 3rd pass	13	10	14	17	18	24	26
   After 4th pass	10	13	14	17	18	24	26
   After 5th pass	10	13	14	17	18	24	26

   Write down the number of comparisons and swaps on each of the five passes.
2. Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.

A student is using a quicksort algorithm to rearrange a set of numbers into ascending order. She uses the first number in each list (or sublist) as the pivot. Her correct solution for the first three passes is as follows. Initial list: 10, 7, 4, 22, 13, 16, 19, 5 After 1st pass: 7, 4, 5, 10, 22, 13, 16, 19 After 2nd pass: 4, 5, 7, 10, 13, 16, 19, 22 After 3rd pass: 4, 5, 7, 10, 13, 16, 19, 22

1. State the pivots used for the 2nd pass. [2]
2. Write down the number of comparisons on each of the three passes. [3]
3. Explain whether the student has completed the algorithm. [1]

The following algorithm is a version of bubble sort. Step 1 \quad Store the values to be sorted in locations L(1), L(2), \(\ldots\) , L(n) and set i to be the number, n, of values to be sorted. Step 2 \quad Set j = 1. Step 3 \quad Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is larger than that in L(j+1). Step 4 \quad Add 1 to j. Step 5 \quad If j is less than i then go to step 3. Step 5 \quad Write out the current list, L(1), L(2), \(\ldots\) , L(n). Step 6 \quad Subtract 1 from i. Step 7 \quad If i is larger than 1 then go to step 2. Step 8 \quad Stop.

1. Apply this algorithm to sort the following list. 109 \quad 32 \quad 3 \quad 523 \quad 58. Count the number of comparisons and the number of swaps which you make in applying the algorithm. [4]
2. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number. [2]
3. Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100 000 values? (Give your answer in hours and minutes.) [2]