D1 June 2013 (R) Q4
4.
1. Sam (S)
2. Janelle (J)
3. Haoyu (H)
4. Alfie (A)
5. Cyrus (C)
6. Komal (K)
7. Polly (P)
8. David (D)
9. Tom (T)
10. Lydia (L)
A binary search is to be performed on the names in the list above to locate the name Lydia.
| Scheme | Marks |
|---|---|
| E.g. a quick sort | |
| S J H A C K P D T L pivot K | M1 |
| J H A C D K S P T L pivots A T | |
| A J H C D K S P L T pivots C P | A1 |
| A C J H D K L P S T pivot H (L) (S) | A1 |
| A C D H J K L P S T | |
| sort completed + named correctly | A1 |
| (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
Additional solutions
Quick sort middle left
| S J H A C K P D T L Pivot C | M1 |
| A C S J H K P D T L Pivots (A) and K | |
| A C J H D K S P T L Pivots H and P | A1 |
| A C D H J K L P S T Pivots (D, J, L) and S | |
| A C D H J K L P S T | A1 |
| Quick sort complete | A1 |
Bubble sort left to right
| S J H A C K P D T L | |
| J H A C K P D S L T T in place, consistent direction | M1 |
| H A C J K D P L S T Passes 1 and 2 correct | A1 |
| A C H J D K L P S T | |
| A C H D J K L P S T | |
| A C D H J K L P S T Sort correct | A1 |
| Bubble Sort complete Sort named correctly + ‘stop’ | A1 |
Bubble sort right to left:
| S J H A C K P D T L | |
| A S J H C D K P L T A in place, consistent direction | M1 |
| A C S J H D K L P T Passes 1 and 2 correct | A1 |
| A C D S J H K L P T | |
| A C D H S J K L P T | |
| A C D H J S K L P T | |
| A C D H J K S L P T | |
| A C D H J K L S P T | |
| A C D H J K L P S T Sort correct | A1 |
| Bubble Sort complete Sort named correctly + ‘stop’ | A1 |
Sorting into reverse alphabetical order is acceptable for full marks
| Scheme | Marks |
|---|---|
| Pivot 1 = \(\left\lceil \frac{1+10}{2}\right\rceil = 6\) Komal, L is after K so reject 1 - 6 | M1 A1 |
| Pivot 2 = \(\left\lceil \frac{7+10}{2}\right\rceil = 9\) Sam, L is before S so reject 9 - 10 | A1 |
| Pivot 3 = \(\left\lceil \frac{7+8}{2}\right\rceil = 8\) Polly, L is before P so reject 8 | |
| Pivot 4 = 7 Lydia – name found | A1 cso |
| (4) | |
| (8 marks) |
Notes
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’