D1 January 2009 Q1
1.
| Max | Lauren | John | Hannah | Kieran | Tara | Richard | Imogen |
(a) Use a quick sort to produce a list of these names in ascending alphabetical order.
You must make your pivots clear. (5)
You must make your pivots clear. (5)
(b) Use the binary search algorithm on your list from part (a) to try to locate the name ‘Hugo’. (4)
| Scheme | Marks |
|---|---|
e.g. | M1 A1 A1ft A1ft A1cso |
| (5) |
Notes
(a) 1M1: quick sort, pivots, p, chosen and two sublists one <p one >p. If choosing 1 pivot per iteration only M1 only.
1A1: first pass correct and next pivots chosen correctly/consistently.
2A1ft: second pass correct, next pivots correctly/consistently chosen.
3A1ft: third pass correct, next pivots correctly/consistently chosen.
4A1: all correct, cso.
| Scheme | Marks |
|---|---|
| 1st choice \(\left[\dfrac{1+8}{2}\right] \to 5\) Lauren reject right | |
| 2nd choice \(\left[\dfrac{1+4}{2}\right] \to 3\) John reject right | M1 A1 |
| 3rd choice \(\left[\dfrac{1+2}{2}\right] \to 2\) Imogen reject right | A1ft |
| 4th choice 1 Hannah reject List now empty so Hugo not in list | A1 |
| (4) | |
| (9 marks) |
Notes
(b) 1M1: binary search, choosing pivot, rejecting half list. If using unsorted list, M0. Accept choice of K for M1 only.
1A1: first pass correct, condone ‘sticky’pivot here, bod.
2A1ft: second pass correct, pivot rejected.
3A1: cso.