| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Comparing Sorting Algorithms |
| Difficulty | Easy -1.2 This is a straightforward pattern-matching exercise requiring recall of standard sorting algorithm behaviors. Students need only recognize characteristic features (bubble sort's sequential swaps, quick sort's pivot partitioning, etc.) and count operations in given solutions—no problem-solving, proof, or novel application required. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| \multirow[t]{4}{*}{Solution 1} | 17 | 3 | 16 | 4 |
| 3 | 17 | 16 | 4 | |
| 3 | 16 | 17 | 4 | |
| 3 | 4 | 16 | 17 | |
| \multirow[t]{3}{*}{Solution 2} | 17 | 3 | 16 | 4 |
| 16 | 3 | 17 | 4 | |
| 3 | 4 | 16 | 17 | |
| \multirow[t]{4}{*}{Solution 3} | 17 | 3 | 16 | 4 |
| 3 | 16 | 4 | 17 | |
| 3 | 16 | 4 | 17 | |
| 3 | 4 | 16 | 17 | |
| \multirow[t]{4}{*}{Solution 4} | 17 | 3 | 16 | 4 |
| 3 | 16 | 4 | 17 | |
| 3 | 4 | 16 | 17 | |
| 3 | 4 | 16 | 17 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| 1 — Shuttle | B1 | For one correct |
| 2 — Shell | B1 | For a second correct |
| 3 — Quick, 4 — Bubble | B1 | For all correct — 3 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Solution | Comparisons | Swaps |
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 3 | 3 |
| 4 | 3 | 3 |
# Question 7(a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| 1 — Shuttle | B1 | For one correct |
| 2 — Shell | B1 | For a second correct |
| 3 — Quick, 4 — Bubble | B1 | For all correct — 3 marks total |
# Question 7(b):
| Solution | Comparisons | Swaps | Marks | Guidance |
|---|---|---|---|---|
| 1 | 1 | 1 | B1, B1 | Tallies: max 6/8 |
| 2 | 2 | 1 | B1, B1 | |
| 3 | 3 | 3 | B1, B1 | |
| 4 | 3 | 3 | B1, B1 | 8 marks total |
---7 The numbers 17, 3, 16 and 4 are to be sorted into ascending order.\\
The following four methods are to be compared: bubble sort, shuttle sort, Shell sort and quick sort (with the first number used as the pivot).
A student uses each of the four methods and produces the correct solutions below. Each solution shows the order of the numbers after each pass.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multirow[t]{4}{*}{Solution 1} & 17 & 3 & 16 & 4 \\
\hline
& 3 & 17 & 16 & 4 \\
\hline
& 3 & 16 & 17 & 4 \\
\hline
& 3 & 4 & 16 & 17 \\
\hline
\multirow[t]{3}{*}{Solution 2} & 17 & 3 & 16 & 4 \\
\hline
& 16 & 3 & 17 & 4 \\
\hline
& 3 & 4 & 16 & 17 \\
\hline
\multirow[t]{4}{*}{Solution 3} & 17 & 3 & 16 & 4 \\
\hline
& 3 & 16 & 4 & 17 \\
\hline
& 3 & 16 & 4 & 17 \\
\hline
& 3 & 4 & 16 & 17 \\
\hline
\multirow[t]{4}{*}{Solution 4} & 17 & 3 & 16 & 4 \\
\hline
& 3 & 16 & 4 & 17 \\
\hline
& 3 & 4 & 16 & 17 \\
\hline
& 3 & 4 & 16 & 17 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Write down which of the four solutions is the bubble sort, the shuttle sort, the Shell sort and the quick sort.
\item For each of the four solutions, write down the number of comparisons and swaps (exchanges) on the first pass.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q7 [11]}}