D1 June 2018 Q2
2. A list of nine numbers needs to be sorted into descending order.
Mayleen used a sorting algorithm to sort a list of nine numbers into descending order.
Mayleen’s list after the first pass through the algorithm is given below.
30 33 35 27 20 24 21 15 19
Given that Mayleen used the quick sort algorithm,
A tenth number, 18, is added to the list of nine numbers.
You must justify your answer. (1)
| Scheme | Marks |
|---|---|
| (If starting at the left hand end of the list then) in the first pass we compare the first value with the second value and we swap these values if the second is larger than the first. We then compare the value which is now second with the third value and swap if the third is larger than the second. We continue in this way until we reach the end of the list | M1 A1 |
| (2) |
Notes
a1M1: Comparing first value with second value, swap if second is larger (oe) – must be clear that the first value in the list is being compared with the second value in the list and swapping if the second is larger than the first (oe)
a1A1: Compare second with third, (and then third with fourth), and so on until the end (or 9th item) of the list – must be clear that after the first comparison the second value in the list is compared with the third value and so on until the end of the list
| Scheme | Marks |
|---|---|
| If sorting from left to right then the smallest number (15) would be in the correct position | B1 |
| If sorting from right to left then the largest number (35) would be in the correct position | B1 |
| (2) |
Notes
b1B1: CAO (for left to right) – must mention either the smallest (oe) or the 15 should be at the end of the list/correct position (bod if 15 is mentioned (but not incorrectly))
b2B1: CAO (for right to left) – must mention either the largest (oe) or the 35 should be at the end of the list/correct position (bod if 35 is mentioned (but not incorrectly))
| Scheme | Marks |
|---|---|
| 27 | B1 |
| (1) |
Notes
c1B1: CAO (27) – B0 if choice of answers
| Scheme | Marks |
|---|---|
| \(30\quad \underline{33}\quad 35\quad \boxed{27}\quad 20\quad 24\quad \underline{21}\quad 15\quad 19\) | |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad 20\quad \underline{15}\quad 19\) | M1 |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad 20\quad \underline{19}\quad \boxed{15}\) | A1 |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad 20\quad \boxed{19}\quad \boxed{15}\) (sort complete) | A1 |
| SEE SC BELOW FOR THOSE USING 20 AS A PIVOT | |
| (3) |
Notes
d1M1: Quick sort – 33 and 21 selected as pivots and after their first pass the sublists must read (values greater than the pivot), pivot, (values less than the pivot)
d1A1: The first ‘two’ passes correct – they do not need to be selecting a pivot for the ‘third’ pass
d2A1: CSO (correct solution only) – must include a ‘third’ pass in which the 19 (or 20 if middle left) is used as a pivot – a ‘sort complete’ statement is not required (as their third pass contains no swaps)
SC for (d): If candidates start the quick sort on the list given in the stem to (b) then award M1 only for 20 chosen as a pivot and after the first pass the list must read 30 33 35 27 24 21 20 15 19In (d) sorting list into ascending order is M0 but allow recovery in (e) if first-fit decreasing
Middle left for (d)
| \(30\quad \underline{33}\quad 35\quad \boxed{27}\quad 20\quad 24\quad \underline{21}\quad 15\quad 19\) | |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad 20\quad \underline{15}\quad 19\) | |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad \underline{20}\quad 19\quad \boxed{15}\) | |
| \(35\quad \boxed{33}\quad 30\quad \boxed{27}\quad 24\quad \boxed{21}\quad \boxed{20}\quad 19\quad \boxed{15}\) |
| Scheme | Marks |
|---|---|
| Bin 1: \(\boxed{35}\ \ \underline{24}\) | M1 |
| Bin 2: \(\boxed{33}\ \ \boxed{27}\) | A1 |
| Bin 3: \(\boxed{30}\ \ \underline{21}\) | A1 |
| Bin 4: \(\underline{20}\ \ 19\ \ 15\) | |
| (3) |
Notes
e1M1: 35 in Bin 1, Bin 2 correct and 30 in Bin 3 (so first 4 values correctly placed) – no follow through on an incorrect list from (d) – condone cumulative totals for M1 only (the boxed values)
e1A1: First 7 values correctly placed (the boxed and underlined values)
e2A1: CSO (so no additional/repeated values)
| Scheme | Marks |
|---|---|
| \(\dfrac{242}{60} = 4.0333\ldots\) so no it is not possible to pack the 10 numbers into 4 bins of size 60 or a wastage argument regarding the maximum possible value of 16 | B1 |
| (1) | |
| (12 marks) |
Notes
f1B1: CSO – therefore correct calculation (e.g. 242/4 = 60.5) + conclusion (oe i.e. an argument based on wastage e.g. there is only room for a tenth value of at most 16)