D1 June 2017 Q3
3.
42 21 15 16 35 10 31 11 27 39
The nine distinct numbers below are to be sorted into descending order
23 14 17 \(x\) 21 18 8 20 11
A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass, the list is
23 17 \(x\) 21 18 14 20 11 8
After the second complete pass, the list is
23 17 21 18 \(x\) 20 14 11 8
| Scheme | Marks |
|---|---|
| Bin 1: \(\boxed{42}\ \ \boxed{21}\) | M1 A1 A1 |
| Bin 2: \(\boxed{15}\ \ \boxed{16}\ \ \underline{10}\ \ \underline{11}\) | |
| Bin 3: \(\boxed{35}\ \ 27\) | |
| Bin 4: \(\underline{31}\) | |
| Bin 5: 39 | |
| (3) |
Notes
a1M1: First five items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the boxed values)
a1A1: First eight items placed correctly (the boxed and underlined values)
a2A1: CSO (so no additional/repeated values)
Misreads- If the candidate has misread a number at the start of (a), so genuinely miscopy a number then mark the whole of (a), (b) and (c) as a misread – removing the last two A marks earned. This gives a maximum of 8 marks in total for these three parts
- If they have used the correct numbers at any point in (a) and then use an incorrect number in (b) (say 24 instead of 42) from the beginning of the sort or misread one of their own numbers during (b) then count it as one ‘error’ in (b) (so they will lose at least the final A mark in (b) but should be able to gain at least the M mark and the follow through A mark) – then mark (c) according to the SC above. More than one ‘error’ in (b) loses all subsequent A marks in (b)
| Scheme | Marks |
|---|---|
| e.g. middle right | M1 |
| \(42\quad 21\quad 15\quad 16\quad 35\quad \underline{10}\quad 31\quad 11\quad 27\quad 39\) Pivot 10 | |
| \(42\quad 21\quad 15\quad 16\quad \underline{35}\quad 31\quad 11\quad 27\quad 39\quad \boxed{10}\) Pivot 35 | A1 |
| \(42\quad \underline{39}\quad \boxed{35}\quad 21\quad 15\quad 16\quad \underline{31}\quad 11\quad 27\quad \boxed{10}\) Pivot 39, 31 | |
| \(42\quad \boxed{39}\quad \boxed{35}\quad \boxed{31}\quad 21\quad 15\quad \underline{16}\quad 11\quad 27\quad \boxed{10}\) Pivots (42) 16 | A1ft |
| \(42\quad \boxed{39}\quad \boxed{35}\quad \boxed{31}\quad 21\quad \underline{27}\quad \boxed{16}\quad 15\quad \underline{11}\quad \boxed{10}\) Pivots 27, 11 | |
| \(42\quad \boxed{39}\quad \boxed{35}\quad \boxed{31}\quad \boxed{27}\quad 21\quad \boxed{16}\quad 15\quad \boxed{11}\quad \boxed{10}\) Sort complete | A1 |
| (4) |
Notes
b1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last 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). If only choosing one pivot per iteration then M1 only – Bubble sort is not a MR and scores M1 only for 42 21 16 35 15 31 11 27 39 10 (for left to right) or 42 39 21 15 16 35 10 31 11 27 (for right to left)
b1A1: First two passes correct and next pivots chosen correctly for the third pass (but the third pass does not need to be correct) – so they must be choosing (if middle right) pivot values of 39 and 31 for the third pass or (if middle left) a pivot value of 16
b2A1ft: Third and fourth passes correct (follow through from their second pass and choice of pivots). They do not need to be choosing a pivot for the fifth pass for this mark
b3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including a fifth pass in which the 27 and 11 (if middle right) or 21 (if middle left) is used as a pivot and a ‘sort complete’ - this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot (which would therefore mean that the final list would have been written twice)
Sorting list into ascending order in (b)- If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (b)
- If the list is not reversed in (b) then mark as a misread (so remove the last two A marks earned in (b)). If the list is reversed at the start of (c) but not in (b) then still treat this as a misread. If the list is in ascending order in (b) award no marks for first-fit increasing in (c). If the candidate says that the list needs reversing in (b) but does not actually show the reversed list in (b) then remove the final A mark
Middle left for (b)
| \(42\quad 21\quad 15\quad 16\quad \underline{35}\quad 10\quad 31\quad 11\quad 27\quad 39\) Pivot 35 | |
| \(\underline{42}\quad 39\quad \boxed{35}\quad 21\quad 15\quad 16\quad \underline{10}\quad 31\quad 11\quad 27\) Pivots 42, 10 | |
| \(\boxed{42}\quad 39\quad \boxed{35}\quad 21\quad 15\quad \underline{16}\quad 31\quad 11\quad 27\quad \boxed{10}\) Pivots (39) 16 | |
| \(\boxed{42}\quad 39\quad \boxed{35}\quad 21\quad \underline{31}\quad 27\quad \boxed{16}\quad \underline{15}\quad 11\quad \boxed{10}\) Pivots 31, 15 | |
| \(\boxed{42}\quad 39\quad \boxed{35}\quad \boxed{31}\quad \underline{21}\quad 27\quad \boxed{16}\quad \boxed{15}\quad 11\quad \boxed{10}\) Pivot 21 (11) | |
| \(\boxed{42}\quad 39\quad \boxed{35}\quad \boxed{31}\quad 27\quad \boxed{21}\quad \boxed{16}\quad \boxed{15}\quad 11\quad \boxed{10}\) Sort complete |
Ascending middle right
| \(42\quad 21\quad 15\quad 16\quad 35\quad \underline{10}\quad 31\quad 11\quad 27\quad 39\) | |
| \(\boxed{10}\quad 42\quad 21\quad 15\quad 16\quad \underline{35}\quad 31\quad 11\quad 27\quad 39\) | |
| \(\boxed{10}\quad 21\quad 15\quad 16\quad \underline{31}\quad 11\quad 27\quad \boxed{35}\quad 42\quad \underline{39}\) | |
| \(\boxed{10}\quad 21\quad 15\quad \underline{16}\quad 11\quad 27\quad \boxed{31}\quad \boxed{35}\quad \boxed{39}\quad 42\) | |
| \(\boxed{10}\quad 15\quad \underline{11}\quad \boxed{16}\quad 21\quad \underline{27}\quad \boxed{31}\quad \boxed{35}\quad \boxed{39}\quad 42\) | |
| \(\boxed{10}\quad \boxed{11}\quad 15\quad \boxed{16}\quad 21\quad \boxed{27}\quad \boxed{31}\quad \boxed{35}\quad \boxed{39}\quad 42\) Sort complete |
Ascending middle left
| \(42\quad 21\quad 15\quad 16\quad \underline{35}\quad 10\quad 31\quad \underline{11}\quad 27\quad 39\) | |
| \(21\quad 15\quad 16\quad \underline{10}\quad 31\quad 11\quad 27\quad \boxed{35}\quad \underline{42}\quad 39\) | |
| \(\boxed{10}\quad 21\quad 15\quad \underline{16}\quad 31\quad 11\quad 27\quad \boxed{35}\quad 39\quad \boxed{42}\) | |
| \(\boxed{10}\quad \underline{15}\quad 11\quad \boxed{16}\quad 21\quad \underline{31}\quad 27\quad \boxed{35}\quad 39\quad \boxed{42}\) | |
| \(\boxed{10}\quad 11\quad \boxed{15}\quad \boxed{16}\quad \underline{21}\quad 27\quad \boxed{31}\quad \boxed{35}\quad 39\quad \boxed{42}\) | |
| \(\boxed{10}\quad 11\quad \boxed{15}\quad \boxed{16}\quad \boxed{21}\quad 27\quad \boxed{31}\quad \boxed{35}\quad 39\quad \boxed{42}\) (Sort complete) |
| Scheme | Marks |
|---|---|
| Bin 1: \(\boxed{42}\ \ \underline{21}\) | M1 A1 A1 |
| Bin 2: \(\boxed{39}\ \ \underline{16}\ \ 10\) | |
| Bin 3: \(\boxed{35}\ \ \boxed{27}\) | |
| Bin 4: \(\boxed{31}\ \ \underline{15}\ \ 11\) | |
| (3) |
Notes
c1M1: Must be using ‘sorted’ list in descending order. First five items placed correctly and at least eight values placed in bins – condone cumulative totals for M1 only (the boxed values)
c1A1: First eight items placed correctly (the underlined and boxed values)
c2A1: CSO (so no additional/repeated values)
SC for part (c) – if ‘sorted’ list is incorrect from part (b) and M0 would be awarded in (c) then award M1 only in (c) for their first eight items correctly placed – by ‘incorrect’ they can have only one ‘error’- an ‘error’ is one missing number, one extra number, or one number incorrectly placed. Allow full marks in (c) if a correct list is used in (c) even if the list is incorrect at the end of (b)| Scheme | Marks |
|---|---|
| \(14 \lt x \lt 17\) | B3,2,1,0 |
| (3) | |
| (13 marks) |
Notes
IN (d) mark their final attempt only – if in doubt please send to reviewd1B1: Any inequality in \(x\) linked with either 14 or 17 (allow in words or using set notation) or an indication of an interval with 14 and 17 but with no inequality sign (or even \(x\)) present
d2B1: Any inequality in \(x\) linked with 14 and 17 (allow in words) or using set notation (14, 17)
d3B1: CAO (allow as two separate inequalities: \(x \gt 14,\ x \lt 17\) (allow without a comma separating the two inequalities), accept \(x \gt 14\) and \(x \lt 17\) but not \(x \gt 14\) or \(x \lt 17\)) - if defined using words only then do not award this mark
SC: award B1B1B0 in (d) for \(15 \leqslant x \leqslant 16\) or [15,16] (no marks for any strict inequalities with 15/16)