| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.8 This is a straightforward algorithmic execution question requiring only mechanical application of quicksort and binary search procedures to a simple list of names. No problem-solving, insight, or mathematical reasoning is needed—just following memorized algorithms step-by-step, making it significantly easier than average A-level maths questions. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
| Hajra | Vicky | Leisham | Alice | Nicky | June | Sharon | Tom | Paul |
| (H) | (V) | (L) | (A) | (N) | (J) | (S) | (T) | (P) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| H V L A N J S T P (N)<br>H L A J N V S T P (A, T)<br>A H L J N S P T V (L, P)<br>A H J L N P S T V (J)<br>A H J L N P S T V | M1 A1 A1ft A1cso | M1: quick sort, pivots, p, chosen and two sublists one <p one >p.<br>1A1: first pass correct and next pivots chosen correctly/consistently.<br>2A1ft: second pass correct, next pivots correctly/consistently chosen.<br>3A1: all correct, cso. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 1st choice \(\left[\frac{1+9}{2}\right]=5\) Nicky, reject 1 - 5<br>2nd choice \(\left[\frac{6+9}{2}\right]=[7.5]=8\) Tom, reject 8 - 9<br>3rd choice \(\left[\frac{6+7}{2}\right]=[6.5]=7\) Sharon, reject 7<br>4th choice 6 Paul name found | M1A1 A1 A1cso | M1A1: binary search on what they think is a alphabetical list, choosing pivot, rejecting half list.<br>1A1: first pass correct, condone 'sticky' pivot here, bod generous.<br>2A1: second pass correct, pivot rejected.<br>3A1: cso.<br><br>Note: If incorrect list in (a) mark (b) as a misread. |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| H V L A N J S T P (N)<br>H L A J N V S T P (A, T)<br>A H L J N S P T V (L, P)<br>A H J L N P S T V (J)<br>A H J L N P S T V | M1 A1 A1ft A1cso | M1: quick sort, pivots, p, chosen and two sublists one <p one >p.<br>1A1: first pass correct and next pivots chosen correctly/consistently.<br>2A1ft: second pass correct, next pivots correctly/consistently chosen.<br>3A1: all correct, cso. |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 1st choice $\left[\frac{1+9}{2}\right]=5$ Nicky, reject 1 - 5<br>2nd choice $\left[\frac{6+9}{2}\right]=[7.5]=8$ Tom, reject 8 - 9<br>3rd choice $\left[\frac{6+7}{2}\right]=[6.5]=7$ Sharon, reject 7<br>4th choice 6 Paul name found | M1A1 A1 A1cso | M1A1: binary search on what they think is a alphabetical list, choosing pivot, rejecting half list.<br>1A1: first pass correct, condone 'sticky' pivot here, bod generous.<br>2A1: second pass correct, pivot rejected.<br>3A1: cso.<br><br>**Note:** If incorrect list in (a) mark (b) as a misread. |
**Total: 8 marks**
---\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Hajra & Vicky & Leisham & Alice & Nicky & June & Sharon & Tom & Paul \\
(H) & (V) & (L) & (A) & (N) & (J) & (S) & (T) & (P) \\
\hline
\end{tabular}
The table shows the names of nine people.
\begin{enumerate}[label=(\alph*)]
\item Use a quick sort to produce the list of names in ascending alphabetical order.
You must make your pivots clear.
[4]
\item Use the binary search algorithm on your list to locate the name Paul.
[4]
\end{enumerate}
(Total 8 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q1 [8]}}