| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.8 This is a straightforward algorithmic execution question requiring only mechanical application of the quicksort algorithm to a small list of 6 numbers. It involves no problem-solving, proof, or conceptual understanding—just following a learned procedure and counting comparisons. This is significantly easier than typical A-level pure maths questions. |
| Spec | 7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Pivot = 17 (middle value). Pass 1: \(2, 12, \mathbf{17}, 18, 5, 13 \rightarrow 2, 12, 5, 13 \mid \mathbf{17} \mid 18\) | M1 | Correct first pivot chosen and items partitioned |
| After pass 1: \(2, 12, 5, 13 \mid \mathbf{17} \mid 18\) | A1 | Correct arrangement after pass 1 |
| Pass 2 pivots: pivot = 12 for left sub-list, giving \(2, 5 \mid \mathbf{12} \mid 13 \mid \mathbf{17} \mid 18\) | M1 | Further correct pivoting on sub-lists |
| Final sorted order: \(2, 5, 12, 13, 17, 18\) | A1 | Fully correct sorted list with all passes shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 5 comparisons | B1 | For the first pass only |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot = 17 (middle value). Pass 1: $2, 12, \mathbf{17}, 18, 5, 13 \rightarrow 2, 12, 5, 13 \mid \mathbf{17} \mid 18$ | M1 | Correct first pivot chosen and items partitioned |
| After pass 1: $2, 12, 5, 13 \mid \mathbf{17} \mid 18$ | A1 | Correct arrangement after pass 1 |
| Pass 2 pivots: pivot = 12 for left sub-list, giving $2, 5 \mid \mathbf{12} \mid 13 \mid \mathbf{17} \mid 18$ | M1 | Further correct pivoting on sub-lists |
| Final sorted order: $2, 5, 12, 13, 17, 18$ | A1 | Fully correct sorted list with all passes shown |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 5 comparisons | B1 | For the first pass only |
---2
\begin{enumerate}[label=(\alph*)]
\item Use the quicksort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. You must indicate the pivot(s) being used on each pass.
$$2 , \quad 12 , \quad 17 , \quad 18 , \quad 5 , \quad 13$$
\item For the first pass, write down the number of comparisons.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q2 [5]}}