2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is
$$\begin{array} { l l l l l l l }
17 & 23 & 84 & 21 & 66 & 35 & 12
\end{array}$$
- How many different possibilities are there for the original list?
Suppose, instead, that the same sort was carried out using bubble sort on the original list.
- Write down the list after two passes through bubble sort.
The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
- For a list of six values, what is the maximum total number of comparisons made in the first two passes of
(a) shuttle sort
(b) bubble sort?
Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes. - Comment on what Steve said.
The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.
| Number of comparisons | 3 | 4 | 5 | 6 |
| Shuttle sort | Number of permutations | 2 | 6 | 8 | 8 |
| Bubble sort | Number of permutations | 1 | 0 | 7 | 16 |
- Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.