D1 June 2010 Q1
1.
| Hajra (H) | Vicky (V) | Leisham (L) | Alice (A) | Nicky (N) | June (J) | Sharon (S) | Tom (T) | Paul (P) |
The table shows the names of nine people.
(a) Use a quick sort to produce the list of names in ascending alphabetical order.
You must make your pivots clear. (4)
You must make your pivots clear. (4)
(b) Use the binary search algorithm on your list to locate the name Paul. (4)
| Scheme | Marks | ||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 A1 A1ft A1cso | ||||||||||||||||||||||||||||||||||||||||||||||||||
| (4) |
Notes
1M1: quick sort, pivots, p, chosen and two sublists one <p one >p.
1A1: first pass correct and next pivots chosen correctly/consistently.
2A1ft: second pass correct, next pivots correctly/consistently chosen.
3A1: all correct, cso.
Q1 Alternative solutions
| Scheme | Marks |
|---|---|
| 1st choice \(\left[\dfrac{1+9}{2}\right] = 5\) Nicky, reject 1 - 5 | M1A1 |
| 2nd choice \(\left[\dfrac{6+9}{2}\right] = [7.5] = 8\) Tom, reject 8 - 9 | A1 |
| 3rd choice \(\left[\dfrac{6+7}{2}\right] = [6.5] = 7\) Sharon, reject 7 | |
| 4th choice 6 Paul name found | A1cso |
| (4) | |
| (8 marks) |
Notes
1M1: binary search on what they think is a alphabetical list, choosing pivot, rejecting half list.
1A1: first pass correct, condone ‘sticky’ pivot here, bod generous
2A1: second pass correct, pivot rejected.
3A1: cso.
Note: If incorrect list in (a) mark (b) as a misread.