| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | September |
| Marks | 8 |
| Topic | Sorting Algorithms |
| Type | Deducing Original List Properties |
| Difficulty | Standard +0.8 This multi-part question requires deep understanding of sorting algorithm mechanics, working backwards from partial results, and statistical analysis of algorithm efficiency. Part (i) demands reverse-engineering shuttle sort (non-trivial), parts (iii-v) require careful counting and comparative analysis across algorithms. While the individual concepts are A-level appropriate, the combination of algorithmic reasoning, combinatorial counting, and justification through expected value calculations makes this substantially harder than typical textbook exercises. |
| Spec | 7.03d Order of algorithm: dominant term and scaling run-times7.03e Efficiency comparison: of two algorithms on specific cases7.03j Sorting: bubble sort and shuttle sort |
| 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 |
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}$$
(i) 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.\\
(ii) 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.\\
(iii) For a list of six values, what is the maximum total number of comparisons made in the first two passes of
\begin{enumerate}[label=(\alph*)]
\item shuttle sort
\item 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.\\
(iv) 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.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Number of comparisons & 3 & 4 & 5 & 6 \\
\hline
Shuttle sort & Number of permutations & 2 & 6 & 8 & 8 \\
\hline
Bubble sort & Number of permutations & 1 & 0 & 7 & 16 \\
\hline
\end{tabular}
\end{center}
(v) Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q2 [8]}}