| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Shuttle Sort Execution |
| Difficulty | Easy -1.8 This is a purely procedural question testing rote execution of the shuttle sort algorithm with no problem-solving required. Part (a) is mechanical application of the algorithm, while parts (b)(i-iii) require only recall of standard shuttle sort properties (n-1 passes, up to k comparisons in pass k+1, and for reverse-sorted lists the swap count formula). This is significantly easier than average A-level maths questions which typically require some mathematical reasoning or technique application. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Initial List \((R \quad E \quad M \quad I \quad X)\) | M1 | Allow working in rows or columns; SCA; i.e. swap E and R only on 1st pass but do not allow a continuation which is clearly bubble sort 2nd pass |
| End of 1st Pass \(E \quad R \quad M \quad I \quad X\) | A1 | |
| End of 2nd Pass \(E \quad M \quad R \quad I \quad X\) | A1 | 3 marks total; All correct |
| End of 3rd Pass \(E \quad I \quad M \quad R \quad X\) | ||
| End of 4th Pass \(E \quad I \quad M \quad R \quad X\) | ||
| (b)(i) 9 (passes) | B1 | In part (b) watch out for candidates answering in the question area rather than the script. |
| (ii) 6 (comparisons) | B1 | |
| (iii) \(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9(+ 10)\) | M1 | or use of \(\frac{n(n+1)}{2}\) with \(n = 9\) or \(n = 10\) |
| 45 | A1 | 4 marks total |
**(a)** Initial List $(R \quad E \quad M \quad I \quad X)$ | M1 | Allow working in rows or columns; SCA; i.e. swap E and R only on 1st pass but do not allow a continuation which is clearly bubble sort 2nd pass
End of 1st Pass $E \quad R \quad M \quad I \quad X$ | A1 |
End of 2nd Pass $E \quad M \quad R \quad I \quad X$ | A1 | 3 marks total; All correct
End of 3rd Pass $E \quad I \quad M \quad R \quad X$ |
End of 4th Pass $E \quad I \quad M \quad R \quad X$ |
**(b)(i)** 9 (passes) | B1 | In part (b) watch out for candidates answering in the question area rather than the script.
**(ii)** 6 (comparisons) | B1 |
**(iii)** $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9(+ 10)$ | M1 | or use of $\frac{n(n+1)}{2}$ with $n = 9$ or $n = 10$
45 | A1 | 4 marks total | 45 scores 2/2 unless clearly from incorrect working (FIW)
**Total: 7 marks**
---2
\begin{enumerate}[label=(\alph*)]
\item Use a shuttle sort to rearrange into alphabetical order the following list of names:\\
Rob, Eve, Meg, lan, Xavi\\
Show the list at the end of each pass.
\item A list of ten numbers is sorted into ascending order, using a shuttle sort.
\begin{enumerate}[label=(\roman*)]
\item How many passes are needed?
\item Give the maximum number of comparisons needed in the sixth pass.
\item Given that the list is initially in descending order, find the total number of swaps needed.\\[0pt]
[4 marks]
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2016 Q2 [7]}}