7.03e Efficiency comparison: of two algorithms on specific cases

7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.

1. The scripts in the 'below 50' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 34 & 42 & 27 & 31 & 12 & 48 & 24 & 37 \end{array}$$ Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.
2. The scripts in the '50 and above' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 95 & 74 & 61 & 87 & 71 & 82 & 53 & 57 \end{array}$$ Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.
3. Explain why splitting the original list into two piles is a linear order algorithm.
4. Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.
   [0pt] [4]

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}$$

1. 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.
2. 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.
3. For a list of six values, what is the maximum total number of comparisons made in the first two passes of
   1. shuttle sort
   2. 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.
   3. 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

   4. Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.