| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a routine algorithmic execution question requiring mechanical application of standard sorting algorithms. Part (a) involves following the quick sort procedure step-by-step with a small list, and part (b) asks for recall of bubble sort properties (maximum swaps = n(n-1)/2 = 28, indicating reverse order). No problem-solving or novel insight required—purely procedural knowledge tested at a basic level. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Using quick sort | M1 | |
| First pass (based on their pivot) | A1 | |
| A correct third pass | A1 | |
| All passes correct | A1 | |
| Consistent pivots clearly labelled (at least three passes) | B1 | 5 |
| B1 | 1 |
| Answer | Marks |
|---|---|
| 28 |
| Answer | Marks | Guidance |
|---|---|---|
| In reverse order | B1 | 1 |
| Allow descending | ||
| Total | 7 |
## 2(a)
| Using quick sort | M1 | |
| First pass (based on their pivot) | A1 | |
| A correct third pass | A1 | |
| All passes correct | A1 | |
| Consistent pivots clearly labelled (at least three passes) | B1 | 5 |
| | B1 | 1 |
## 2(b)(i)
| 28 | | |
## 2(b)(ii)
| In reverse order | B1 | 1 |
| | | Allow descending |
| Total | | 7 |2
\begin{enumerate}[label=(\alph*)]
\item Use a quick sort to rearrange the following letters into alphabetical order. You must indicate the pivot that you use at each pass.\\
P\\
B\\
M\\
N\\
J\\
K\\
R\\
D\\
(5 marks)
\item \begin{enumerate}[label=(\roman*)]
\item Find the maximum number of swaps needed to rearrange a list of 8 numbers into ascending order when using a bubble sort.\\
(1 mark)
\item A list of 8 numbers was rearranged into ascending order using a bubble sort. The maximum number of swaps was needed. What can be deduced about the original list of numbers?\\
(1 mark)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q2 [7]}}