| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Binary Search Execution |
| Difficulty | Easy -1.8 This is a routine algorithmic execution question requiring students to apply bubble sort (or similar) then binary search by rote following standard procedures. It involves no problem-solving, mathematical insight, or novel thinking—just mechanical application of memorized algorithms with bookwork steps. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort |
**Question 4 Notes:**
- a1M1: Quick sort – pivots, p, selected and first pass gives <p, p, >p
- a1A1: First two passes correct, pivots chosen consistently for third pass
- a2A1: CAO sort completed correctly
- a3A1: 'Stop' + correct name for their sort – phonetically close
- b1M1: Using their 'sorted list' + choosing middle right pivots+ discarding/retaining half the list. If their list contains one error (one error is either a missing letter, an extra letter or one letter incorrectly placed) then M1 only in part (b)
- b1A1: First pass correct i.e. 6th item from a correct list and retaining L – T (no sticky pivots)
- b2A1: Second and third passes correct i.e. 9th (S) and 8th (P) items from a correct list (no sticky pivots)
- b3A1: CSO search complete + 'found'
**Additional solutions:**
Quick sort middle left: Pivot C, then pivots (A) and K, then pivots H and P, then pivots (D, J, L) and S, sort completed and named correctly.
Bubble sort left to right: T in place consistent direction, passes 1 and 2 correct, sort correct, sort named correctly + 'stop'.
Bubble sort right to left: A in place, consistent direction, passes 1 and 2 correct, sort correct, sort named correctly + 'stop'.
Sorting into reverse alphabetical order is acceptable for full marks4.
\begin{enumerate}
\item Sam (S)
\item Janelle (J)
\item Haoyu (H)
\item Alfie (A)
\item Cyrus (C)
\item Komal (K)
\item Polly (P)
\item David (D)
\item Tom (T)
\item Lydia (L)
\end{enumerate}
A binary search is to be performed on the names in the list above to locate the name Lydia.\\
\begin{enumerate}[label=(\alph*)]
\item Using an appropriate algorithm, rearrange the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
\item Use the binary search algorithm to locate the name Lydia in the list you obtained in (a). You must make your method clear.\\
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q4 [8]}}