| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Maximum Comparisons or Swaps |
| Difficulty | Easy -1.2 This question tests pure recall of standard sorting algorithm properties with no problem-solving required. Each part asks for a memorized fact about comparison counts (quicksort first pass: n-1=15, Shell sort first pass depends on gap sequence, shuttle sort final pass: 1, bubble sort maximum: n(n-1)/2=120). No derivation, insight, or multi-step reasoning needed—just direct application of learned formulas. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(15\) comparisons | B1 | quicksort first pass on 16 numbers: pivot compared with remaining \(n-1\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(8\) comparisons | B1 | Shell sort first pass: 16 numbers with gap 8, giving 8 comparisons |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(1\) comparison | B1 | minimum on final pass of shuttle sort (already sorted sub-list) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum total for bubble sort on 16 numbers \(= \frac{16 \times 15}{2} = 120\) | M1 | correct use of \(\frac{n(n-1)}{2}\) |
| \(120\) comparisons | A1 | correct answer |
# Question 3:
**(a)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $15$ comparisons | B1 | quicksort first pass on 16 numbers: pivot compared with remaining $n-1$ |
**(b)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $8$ comparisons | B1 | Shell sort first pass: 16 numbers with gap 8, giving 8 comparisons |
**(c)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $1$ comparison | B1 | minimum on final pass of shuttle sort (already sorted sub-list) |
**(d)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum total for bubble sort on 16 numbers $= \frac{16 \times 15}{2} = 120$ | M1 | correct use of $\frac{n(n-1)}{2}$ |
| $120$ comparisons | A1 | correct answer |3 Four students, $A , B , C$ and $D$, are using different algorithms to sort 16 numbers into ascending order.
\begin{enumerate}[label=(\alph*)]
\item Student $A$ uses the quicksort algorithm.
State the number of comparisons on the first pass.
\item Student $B$ uses the Shell sort algorithm.
State the number of comparisons on the first pass.
\item Student $C$ uses the shuttle sort algorithm.
State the minimum number of comparisons on the final pass.
\item Student $D$ uses the bubble sort algorithm.
Find the maximum total number of comparisons.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q3 [5]}}