D1 June 2009 Q4
4.
| Miri | Jessie | Edward | Katie | Hegg | Beth | Louis | Philip | Natsuko | Dylan |
(a) Use the quick sort algorithm to sort the above list into alphabetical order. (5)
(b) Use the binary search algorithm to locate the name Louis. (4)
| Scheme | Marks |
|---|---|
 | M1 1A1 2A1ft 3A1ft 4A1 |
| (5) |
Notes
(a) 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.
| Scheme | Marks |
|---|---|
| \(\left[\dfrac{1+10}{2}\right] = 6\) Katie reject left | M1 |
| \(\left[\dfrac{7+10}{2}\right] = 9\) Natsuko reject right | 1A1 |
| \(\left[\dfrac{7+8}{2}\right] = 8\) Miri reject right | 2A1ft |
| 7 = Louis name found | 3A1 |
| (4) | |
| (9 marks) |
Notes
(b) 1M1: 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.
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