D1 June 2011 Q1
1.
| 1. | Jenny |
| 2. | Merry |
| 3. | Charles |
| 4. | Ben |
| 5. | Toby |
| 6. | Hyo |
| 7. | Kim |
| 8. | Richard |
| 9. | Greg |
| 10. | Freya |
A binary search is to be performed on the names in the list above to locate the name Kim.
| Scheme | Marks |
|---|---|
| The list is not in alphabetical order. | B1 |
| (1) |
Notes
(a) B1 CAO – phonetically close
| Scheme | Marks |
|---|---|
E.g. A Quick sort | M1 A1 A1 |
| Sort complete + named correctly | A1= B1 |
| (4) |
Notes
(b) M1 Quick sort – pivots, p, selected and first pass gives <p, p, >p.
1A1 First two passes correct, pivots chosen consistently for third pass
2A1 CAO Sort completed correctly
3A1=2B1 ‘Stop’ + plus correct name for their sort – phonetically close
Q1 b Additional solutions
Quick sort middle left
M1, A1, A1, A1 Quick sort complete
Bubble sort left to right
| J | M | C | B | T | H | K | R | G | F | |
| J | C | B | M | H | K | R | G | F | T | T in place, consistent direction M1 |
| C | B | J | H | K | M | G | F | R | T | |
| B | C | H | J | K | G | F | M | R | T | Passes 1 and 2 correct A1 |
| B | C | H | J | G | F | K | M | R | T | |
| B | C | H | G | F | J | K | M | R | T | |
| B | C | G | F | H | J | K | M | R | T | |
| B | C | F | G | H | J | K | M | R | T | Sort correct A1 |
Bubble sort complete sort named correctly + ‘stop’ A1
Bubble right to left
| J | M | C | B | T | H | K | R | G | F | |
| B | J | M | C | F | T | H | K | R | G | B in place, consistent direction M1 |
| B | C | J | M | F | G | T | H | K | R | |
| B | C | F | J | M | G | H | T | K | R | Passes 1 and 2 correct A1 |
| B | C | F | G | J | M | H | K | T | R | |
| B | C | F | G | H | J | M | K | R | T | |
| B | C | F | G | H | J | K | M | R | T | Sort correct A1 |
Bubble sort complete sort named correctly + ‘stop’ A1
Sorting into reverse alphabetical order – this is acceptable
e.g. Quick sort middle right
M1, A1, A1, A1 Quick sort complete
| Scheme | Marks |
|---|---|
| Pivot 1 = \(\left[\dfrac{1+10}{2}\right] = 6\) Jenny reject 1 - 6 | M1 A1 |
| Pivot 2 = \(\left[\dfrac{7+10}{2}\right] = 9\) Richard reject 9 - 10 | A1ft |
| Pivot 3 = \(\left[\dfrac{7+8}{2}\right] = 8\) Merry reject 8 | |
| Pivot 4 = 7 Kim - name found | A1 |
| (4) | |
| (9 marks) |
Notes
(c) M1 Using their ‘sorted list’ + choosing middle right pivots+ discarding/retaining half the list. It their list is not in full alphabetical order M1 only.
1A1 First pass correct ie 6th item for a correct list (no sticky pivots)
2A1 Second and third passes correct ie 9th and 8th items from a correct list (no sticky pivots)
3A1 CSO search complete + ‘found’