AS June 2024 Q1
1.
| 4 | 6.5 | 7 | 1.3 | 2 | 5 | 1.5 | 6 | 4.5 | 6 | 1 |
The list of eleven numbers shown above is to be sorted into descending order.
A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is
| 4.5 | 5.6 | 3.8 | 6.7 | 5.4 | 1.6 | 4.8 | 9.1 | 3.3 | 1.7 | 1.5 |
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Middle right pivot(s)
| M1 A1 A1 | 1.1b 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (3) |
Notes
M1: Quick sort – pivots, p, selected and first pass gives >p, p, <p/ If choosing 1 pivot per iteration, award M1 only. Using bubble sort is M0. If sorting into ascending order, pivots chosen for second pass M1 only. If inconsistent with middle left / middle right M1 only.
A1: Second and third passes correct.
A1: CSO – including fourth pass.
Miscopy/misread can score a maximum of M1A0A0
Candidates may put the 6 pivot “second”, if they do, there is an additional pivot required for both middle left and middle right:
Middle right pivot(s)
| 4 | 6.5 | 7 | 1.3 | 2 | \(\boxed{5}\) | 1.5 | 6 | 4.5 | 6 | 1 |
| 6.5 | 7 | \(\boxed{6}\) | 6 | \(\underline{5}\) | 4 | 1.3 | 2 | \(\boxed{1.5}\) | 4.5 | 1 |
| 6.5 | \(\boxed{7}\) | 6 | \(\underline{6}\) | \(\underline{5}\) | 4 | \(\boxed{2}\) | 4.5 | \(\underline{1.5}\) | 1.3 | \(\boxed{1}\) |
| \(\underline{7}\) | 6.5 | \(\boxed{6}\) | \(\underline{6}\) | \(\underline{5}\) | 4 | \(\boxed{4.5}\) | \(\underline{2}\) | \(\underline{1.5}\) | 1.3 | \(\underline{1}\) |
| \(\underline{7}\) | 6.5 | \(\underline{6}\) | \(\underline{6}\) | \(\underline{5}\) | \(\underline{4.5}\) | 4 | \(\underline{2}\) | \(\underline{1.5}\) | 1.3 | \(\underline{1}\) |
Middle left pivots
| 4 | 6.5 | 7 | 1.3 | 2 | \(\boxed{5}\) | 1.5 | 6 | 4.5 | 6 | 1 |
| 6.5 | \(\boxed{7}\) | 6 | 6 | \(\underline{5}\) | 4 | 1.3 | \(\boxed{2}\) | 1.5 | 4.5 | 1 |
| \(\underline{7}\) | 6.5 | \(\boxed{6}\) | 6 | \(\underline{5}\) | \(\boxed{4}\) | 4.5 | \(\underline{2}\) | 1.3 | \(\boxed{1.5}\) | 1 |
| \(\underline{7}\) | \(\boxed{6.5}\) | 6 | \(\underline{6}\) | \(\underline{5}\) | 4.5 | \(\underline{4}\) | \(\underline{2}\) | \(\underline{1.5}\) | \(\boxed{1.3}\) | 1 |
| \(\underline{7}\) | \(\underline{6.5}\) | 6 | \(\underline{6}\) | \(\underline{5}\) | 4.5 | \(\underline{4}\) | \(\underline{2}\) | \(\underline{1.5}\) | \(\underline{1.3}\) | 1 |
| Scheme | Marks | AO |
|---|---|---|
| Bin 1: \(\boxed{7}\) \(\underline{2}\) 1 Bin 2: \(\boxed{6.5}\) \(\underline{1.5}\) 1.3 Bin 3: \(\boxed{6}\) \(\underline{4}\) Bin 4: \(\boxed{6}\) Bin 5: \(\boxed{5}\) \(\boxed{4.5}\) | M1 A1 A1 | 1.1b 1.1b 1.1b |
| (3) |
Notes
M1: First six items placed correctly (the values in boxes) with at least eight values placed – allow cumulative totals for M1 only.
A1: First nine items placed correctly (the values in boxes and underlined).
A1: CSO (therefore no repeated values)
| Scheme | Marks | AO |
|---|---|---|
| Lower bound for the number of rolls required is given by \[\frac{4 + 6.5 + 7 + 1.3 + 2 + 5 + 1.5 + 6 + 4.5 + 6 + 1}{10}\]\(= \dfrac{44.8}{10} = 4.48\) | M1 | 1.1b |
| Therefore the minimum number of bins is 5 Yes, the solution is optimal | A1 | 2.2a |
| (2) |
Notes
M1: Either Lower bound calculation attempted ([37.5,51.8] / 10) (accept sight of 4.48)
or Total wastage calculation attempted and compared with 10
or Total space used and compared with 50
or a clear statement that four values are over half the bin capacity and one is equal to half, therefore the minimum number of bins must be 5.
A1: CSO This mark is dependent on the correct bin packing in (b). Requires two things;
a statement “minimum 5 bins” is sufficient and a correct numerical argument.
This could be either a correct calculation (4.48)
or a correct numerical justification for why the answer to (b) does use the minimum number of bins.
| Scheme | Marks | AO |
|---|---|---|
| e.g. The lowest two values should be in the two far right positions, and they are not. OR 1.6 is not in the correct position | B1 | 3.1a |
| (1) | ||
| (9 marks) |
Notes
B1: Allow candidates to only consider the right-hand end of the given list (i.e. condone omission of considering the left-hand end).
Must mention either the two smallest values being in the tenth and eleventh positions is not the case, or clearly state that the second smallest value (1.6) is not in the correct position.
Alternatively, may consider both ends with statement e.g. the two (largest) numbers not in order at one end and the two (smallest) numbers not in order at the other end.