| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.8 This is a purely procedural question requiring mechanical application of standard algorithms with no problem-solving or mathematical insight. Students simply follow the quick sort steps on a given list and then apply binary search—both are rote procedures from the D1 specification requiring only recall and careful execution. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| Answer showing 6 passes of quick sort with table progressing through iterations | M1 1A1; 2A1ft; 3A1ft; 4A1 | (5) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(\left\lfloor \frac{1+10}{2} \right\rfloor = 6\) Katie reject left | M1 | Binary search, choosing pivot rejecting half list. If using unordered list then M0. If choosing J M1 ony. 1A1: first two passes correct, condone 'sticky' pivots here, bod. |
| Answer: \(\left\lfloor \frac{7+10}{2} \right\rfloor = 9\) Natsuko reject right | 1A1 | 2A1ft: third pass correct, pivots rejected. 3A1: cso, including success statement. |
Answer showing 6 passes of quick sort with table progressing through iterations | M1 1A1; 2A1ft; 3A1ft; 4A1 | (5) | 1M1: quick sort, pivots, p. identified, two sublists one $<p$ one $>p$. **If choosing one pivot only per iteration, M1 only.** 1A1: first pass correct, next pivot(s) chosen consistently. 2A1ft: second pass correct, next pivot(s) chosen consistently. 3A1ft: third pass correct, next pivot(s) chosen consistently. 4A1: cso List re-written or end statement made or each element been chosen as a pivot.
**Part (b)**
Answer: $\left\lfloor \frac{1+10}{2} \right\rfloor = 6$ Katie reject left | M1 | Binary search, choosing pivot rejecting half list. **If using unordered list then M0. If choosing J M1 ony.** 1A1: first two passes correct, condone 'sticky' pivots here, bod.
Answer: $\left\lfloor \frac{7+10}{2} \right\rfloor = 9$ Natsuko reject right | 1A1 | 2A1ft: third pass correct, pivots rejected. 3A1: cso, including success statement.
**Special case for (b)** – If just one letter out of order, award maximum of M1A1A0A0
---4.
Miri\\
Jessie\\
Edward\\
Katie\\
Hegg\\
Beth\\
Louis\\
Philip\\
Natsuko\\
Dylan
\begin{enumerate}[label=(\alph*)]
\item Use the quick sort algorithm to sort the above list into alphabetical order.\\
(5)
\item Use the binary search algorithm to locate the name Louis.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q4 [9]}}