| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Shell Sort Execution |
| Difficulty | Easy -1.2 This is a straightforward procedural question requiring mechanical application of the Shell sort algorithm with a small dataset (8 elements). It tests recall and careful execution of a standard algorithm rather than problem-solving or mathematical insight, making it easier than average A-level questions. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Split into groups of 4 and 4: \([7\ 8\ 1\ 6]\ [3\ 4\ 5\ 2]\), merge-sort each half | M1 | Correct shell sort split and first pass shown |
| After first pass: \(1\ 6\ 7\ 8\ 2\ 3\ 4\ 5\) (or equivalent correct intermediate) | A1 | Correct result after first pass |
| After second pass: \(1\ 2\ 3\ 6\ 4\ 5\ 7\ 8\) (merging) | A1 | Correct second pass |
| Final sorted: \(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\) | A1 | Correct final answer |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(4\) comparisons on the first pass | B1 | Accept 4 |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Split into groups of 4 and 4: $[7\ 8\ 1\ 6]\ [3\ 4\ 5\ 2]$, merge-sort each half | M1 | Correct shell sort split and first pass shown |
| After first pass: $1\ 6\ 7\ 8\ 2\ 3\ 4\ 5$ (or equivalent correct intermediate) | A1 | Correct result after first pass |
| After second pass: $1\ 2\ 3\ 6\ 4\ 5\ 7\ 8$ (merging) | A1 | Correct second pass |
| Final sorted: $1\ 2\ 3\ 4\ 5\ 6\ 7\ 8$ | A1 | Correct final answer |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $4$ comparisons on the first pass | B1 | Accept 4 |
---2
\begin{enumerate}[label=(\alph*)]
\item Use a Shell sort to arrange the following numbers into ascending order.
$$\begin{array} { l l l l l l l l }
7 & 8 & 1 & 6 & 3 & 4 & 5 & 2
\end{array}$$
\item Write down the number of comparisons on the first pass.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q2 [5]}}