| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Counting Comparisons and Swaps |
| Difficulty | Easy -1.8 This is a straightforward recall and application question on the quicksort algorithm. Students need only trace through given work to identify pivots (7 and 22), count comparisons by inspection (7, 5, 3), and recognize the list is sorted. No problem-solving or novel insight required—purely algorithmic bookwork with minimal computational demand. |
| Spec | 7.03k Sorting: quick sort |
A student is using a quicksort algorithm to rearrange a set of numbers into ascending order. She uses the first number in each list (or sublist) as the pivot.
Her correct solution for the first three passes is as follows.
Initial list: 10, 7, 4, 22, 13, 16, 19, 5
After 1st pass: 7, 4, 5, 10, 22, 13, 16, 19
After 2nd pass: 4, 5, 7, 10, 13, 16, 19, 22
After 3rd pass: 4, 5, 7, 10, 13, 16, 19, 22
\begin{enumerate}[label=(\alph*)]
\item State the pivots used for the 2nd pass. [2]
\item Write down the number of comparisons on each of the three passes. [3]
\item Explain whether the student has completed the algorithm. [1]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q2 [6]}}