A2 June 2025 Q2
2.
| 271 | 828 | 182 | 845 | 904 | 523 | 536 | 028 | 747 | 135 |
The list of ten numbers above is to be sorted into descending order.
A list of \(n\) numbers is to be sorted into descending order using bubble sort.
The following algorithm determines an approximation to the value of e
| Step 1 | Start |
| Step 2 | Let \(a = 1\) |
| Step 3 | Let \(b = 1\) |
| Step 4 | Let \(c = 1\) |
| Step 5 | Let \(d = a\) |
| Step 6 | Let \(c = c \times b\) |
| Step 7 | Let \(d = d + \frac{1}{c}\) |
| Step 8 | If \(b = 6\) go to Step 11 |
| Step 9 | Let \(b = b + 1\) |
| Step 10 | Go to Step 6 |
| Step 11 | Output \(d\) |
| Step 12 | Stop |
[The table in the answer book has columns headed \(a\), \(b\), \(c\), \(d\). You may not need to use all the rows in this table. It may not be necessary to complete all boxes in each row.]
| \(a\) | \(b\) | \(c\) | \(d\) |
|---|---|---|---|
| Scheme | Marks | AO | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e.g. Middle right
| M1 A1 A1ft A1 | 1.1b 1.1b 1.1b 1.1b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Middle left
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (4) |
Notes
a1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing any other item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less that the pivot). Condone one error or omission in the list.
If only choosing one pivot per iteration then max of M1 only
Bubble sort is not a MR and scores M0.
If the list is sorted into ascending order, they can score M1 A1 A0 A0 for a fully correct sort even if reversed (if any error seen this can score M1 only).
If 028 is written as 28 at any stage this will lose the final CSO mark
The choice of pivots may only be seen once they have been used
a1A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct)
a2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots). They do not need to be choosing a pivot for the fourth pass for this mark
If they alternate MR and ML pivots for the first and second passes, the pivots for the third pass must be consistent with their second pass
a3A1: CSO – so must have chosen and used 747 (MR) or 828 (ML) as a pivot for the fifth pass
Sort Ascending Max M1 A1 A0 A0 e.g Middle right
| Pivots | ||||||||||
| 271 | 828 | 182 | 845 | 904 | 523 | 536 | 028 | 747 | 135 | 523 |
| 271 | 182 | 028 | 135 | \(\underline{\text{523}}\) | 828 | 845 | 904 | 536 | 747 | 028, 904 |
| \(\underline{\text{028}}\) | 271 | 182 | 135 | \(\underline{\text{523}}\) | 828 | 845 | 536 | 747 | \(\underline{\text{904}}\) | 182, 536 |
| \(\underline{\text{028}}\) | 135 | \(\underline{\text{182}}\) | 271 | \(\underline{\text{523}}\) | \(\underline{\text{536}}\) | 828 | 845 | 747 | \(\underline{\text{904}}\) | 845 |
| \(\underline{\text{028}}\) | \(\underline{\text{135}}\) | \(\underline{\text{182}}\) | \(\underline{\text{271}}\) | \(\underline{\text{523}}\) | \(\underline{\text{536}}\) | 828 | 747 | \(\underline{\text{845}}\) | \(\underline{\text{904}}\) | 747 |
| \(\underline{\text{028}}\) | \(\underline{\text{135}}\) | \(\underline{\text{182}}\) | \(\underline{\text{271}}\) | \(\underline{\text{523}}\) | \(\underline{\text{536}}\) | \(\underline{\text{747}}\) | 828 | \(\underline{\text{845}}\) | \(\underline{\text{904}}\) |
Middle left
| Pivots | ||||||||||
| 271 | 828 | 182 | 845 | 904 | 523 | 536 | 028 | 747 | 135 | 904 |
| 271 | 828 | 182 | 845 | 523 | 536 | 028 | 747 | 135 | \(\underline{\text{904}}\) | 523 |
| 271 | 182 | 028 | 135 | \(\underline{\text{523}}\) | 828 | 845 | 536 | 747 | \(\underline{\text{904}}\) | 182, 845 |
| 028 | 135 | \(\underline{\text{182}}\) | 271 | \(\underline{\text{523}}\) | 828 | 536 | 747 | \(\underline{\text{845}}\) | \(\underline{\text{904}}\) | 028, 536 |
| \(\underline{\text{028}}\) | 135 | \(\underline{\text{182}}\) | \(\underline{\text{271}}\) | \(\underline{\text{523}}\) | \(\underline{\text{536}}\) | 828 | 747 | \(\underline{\text{845}}\) | \(\underline{\text{904}}\) | 828 |
| \(\underline{\text{028}}\) | \(\underline{\text{135}}\) | \(\underline{\text{182}}\) | \(\underline{\text{271}}\) | \(\underline{\text{523}}\) | \(\underline{\text{536}}\) | 747 | 828 | \(\underline{\text{845}}\) | \(\underline{\text{904}}\) |
| Scheme | Marks | AO |
|---|---|---|
| In the worst case, the first pass requires \((n-1)\) comparisons, the second \((n-2)\), and so on | M1 | 3.1a |
| \(\displaystyle\sum_{r=1}^{n-1} r = \frac{1}{2}n(n-1)\) | A1 | 2.2a |
| (2) |
Notes
b1M1: Considering the total number of comparisons in the worst case (possibly will see e.g. \((n-1) + (n-2) + \ldots [+\, 2 + 1]\) which scores this mark (brackets not needed and sufficient terms to make sum clear. Accept a clear list without + signs for this mark)
b1A1: Using the standard series result that \(\sum r = \frac{1}{2}n(n+1)\) with \(n = (n-1)\) to get the correct quadratic expression for the total number of comparisons when sorting \(n\) values using bubble sort (allow any letter) Accept \((n-1) + (n-2) + \ldots + 2 + 1 = \frac{1}{2}n(n-1)\) for both marks (sight of \(\frac{1}{2}n(n-1)\) with no working scores both marks) (ISW if correct expression incorrectly expanded)
| Scheme | Marks | AO | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 A1 | 1.1b 1.1b | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Output is \(\frac{1957}{720}\) (accept 2.7180555… or 2.72 if working to 3 s.f.) | A1 | 2.2a | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
SC Accept
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (3) |
Notes
Note: Rows are shown above, and they may be spread across multiple rows in the table. Each row ends when the appropriate value in column d is seen
c1M1: At least four rows of cells completed with a correct first and second row – condone repeated values in all columns or a single value in each row (Note SC accept Column B with 1, 2, 3, 4, 5, 6 with no empty cell between 1 and 2)
c1A1: CAO – the values in the third, fourth and fifth rows correct (accept either full recurring decimals or decimals consistently rounded to 3 significant figures)
c2A1: CAO - correct output following a correct seventh row (their output must be clearly indicated e.g. on the Output line or identified in or near the table) If a value is written on the output line, this takes precedence over the table.
| Scheme | Marks | AO |
|---|---|---|
| \(\dfrac{\left|\frac{1957}{720} - \mathrm{e}\right|}{\mathrm{e}} \times 100 = 0.00832(\%)\) If using 2.72 error = 0.0632(%) | B1ft | 3.2b |
| (1) | ||
| (10 marks) |
Notes
d1B1ft: Follow through their answer to (c) provided that % error is < 0.1% (must be given to at least 3 significant figures) (condone missing %) (accept - 0.00832%) (if a numerical approximation to e is used, it must be given to at least 3 d.p. – so 2.718 or better) (accept \(8.32 \times 10^{-3}\)). If incorrect working is seen, even if followed by a correct answer, this is B0.
Note \(\dfrac{\left|\frac{1957}{720} - \mathrm{e}\right|}{\frac{1957}{720}} \times 100 = 0.00832\%\) scores B0