D1 June 2015 Q2

EdexcelOld spec11 marksAlgorithms

18 29 48 9 42 31 37 24 27 41

The numbers above are Alan’s batting scores for the first 10 cricket matches of the season.

(a) Use a quick sort to sort this list of numbers into ascending order. You must make your pivots clear. (4)

Alan’s batting scores for the final 10 cricket matches of the same season were

72 53 89 91 68 67 90 77 83 75

(b) Carry out a bubble sort on this second list of numbers to produce a list of these scores in ascending order. You need only give the state of the list after each pass. (4)

Alan’s combined batting scores for the entire season were

9 18 24 27 29 31 37 41 42 48 53 67 68 72 75 77 83 89 90 91

Mark scheme (a)

Scheme	Marks
e.g. using middle right	M1 (quick)
\(18\quad 29\quad 48\quad 9\quad 42\quad \boxed{31}\quad 37\quad 24\quad 27\quad 41\) pivot 31	A1 (1^st pass/pivots for 2^nd pass)
\(18\quad 29\quad \boxed{9}\quad 24\quad 27\quad \underline{31}\quad 48\quad 42\quad \boxed{37}\quad 41\) pivots 9, 37
\(\underline{9}\quad 18\quad 29\quad \boxed{24}\quad 27\quad \underline{31}\quad \underline{37}\quad 48\quad \boxed{42}\quad 41\) pivots 24, 42	A1ft (2^nd/3^rd passes and pivot(s) for 4^th pass)
\(\underline{9}\quad 18\quad \underline{24}\quad 29\quad \boxed{27}\quad \underline{31}\quad \underline{37}\quad 41\quad \underline{42}\quad 48\) pivot(s) (18), 27, (41), (48)
\(\underline{9}\quad 18\quad \underline{24}\quad \underline{27}\quad 29\quad \underline{31}\quad \underline{37}\quad 41\quad \underline{42}\quad 48\) sort complete (pivot (29))	A1 (cso + sort complete)
	(4)

Notes

a1M1: Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as pivot is M0) and first pass gives <p, p, >p. So after the first pass the list should read (values less than the pivot), pivot, (values greater than the pivot). If only choosing one pivot per iteration M1 only

a1A1: First pass correct and next pivot(s) chosen correctly for second pass (but second pass does not need to be correct)

a2A1ft: Second and third passes correct (follow through from their first pass and choice of pivots) – and next pivot(s) chosen correctly for the fourth pass

a3A1: CSO (correct solution only – all previous marks in this part must have been awarded) including ‘sort complete’ – this could be shown by the final list being re-written or ‘sorted’ statement or each item being used as a pivot

Sorting list into descending order in either (a) and/or (b)

If the candidate sorts the list into descending order and reverses the list then they can score full marks
If the list is not reversed then mark as a misread (so remove the last two A marks earned). If the candidate says that the list needs reversing but doesn’t actually show the reversed list then remove the final A mark earned

Misreads – if there is a ‘misread’ of a single number (this could take the form of an extra number, a number missing, or a number changed, for example, 13 rather than 31) before starting either sort or the binary search then mark as a misread. If they ‘misread’ more than one number then M0. If they miscopy one of their own numbers during the sort then this is an accuracy error and loses the corresponding A mark(s)

Using middle left quick sort in (a)

(note: for full marks must identify 24 as a pivot but no sort complete statement required as pivoting on the 24 produces no further swaps)

\(18\quad 29\quad 48\quad 9\quad 42\quad 31\quad 37\quad 24\quad 27\quad 41\) pivot 42
\(18\quad 29\quad 9\quad 31\quad 37\quad 24\quad 27\quad 41\quad 42\quad 48\) pivot(s) 31, (48)
\(18\quad 29\quad 9\quad 24\quad 27\quad 31\quad 37\quad 41\quad 42\quad 48\) pivots 9, 37
\(9\quad 18\quad 29\quad 24\quad 27\quad 31\quad 37\quad 41\quad 42\quad 48\) pivot(s) 29, (41)
\(9\quad 18\quad 24\quad 27\quad 29\quad 31\quad 37\quad 41\quad 42\quad 48\) pivot 24
\(9\quad 18\quad 24\quad 27\quad 29\quad 31\quad 37\quad 41\quad 42\quad 48\) (sort complete)

Mark scheme (b)

Scheme	Marks
e.g. left to right \(72\quad 53\quad 89\quad 91\quad 68\quad 67\quad 90\quad 77\quad 83\quad 75\)	M1 (bubble)
(end of 1^st pass): \(53\quad 72\quad 89\quad 68\quad 67\quad 90\quad 77\quad 83\quad 75\quad \boxed{91}\)	A1 (1^st and 2^nd passes)
(end of 2^nd pass): \(53\quad 72\quad 68\quad 67\quad 89\quad 77\quad 83\quad 75\quad \boxed{90\quad 91}\)
(end of 3^rd pass): \(53\quad 68\quad 67\quad 72\quad 77\quad 83\quad 75\quad \boxed{89\quad 90\quad 91}\)	A1ft (3^rd and 4^th passes)
(end of 4^th pass): \(53\quad 67\quad 68\quad 72\quad 77\quad 75\quad \boxed{83\quad 89\quad 90\quad 91}\)
(end of 5^th pass): \(53\quad 67\quad 68\quad 72\quad 75\quad \boxed{77\quad 83\quad 89\quad 90\quad 91}\) sort complete	A1 (cso + sort complete)
	(4)

Notes

b1M1: Bubble sort. Consistent direction, end number (greatest/least) in place. Do check these carefully as some candidates show the result of each comparison and swap in the first pass

b1A1: First and second passes correct – so end two numbers in place

b2A1ft: Third and fourth passes correct following through from the candidate’s second pass

b3A1: CSO (correct solution only) – including either a ‘sort complete’ statement or final list rewritten/sixth pass

Right to left bubble sort in (b)

\(72\quad 53\quad 89\quad 91\quad 68\quad 67\quad 90\quad 77\quad 83\quad 75\)
(end of 1^st pass): \(53\quad 72\quad 67\quad 89\quad 91\quad 68\quad 75\quad 90\quad 77\quad 83\)
(end of 2^nd pass): \(53\quad 67\quad 72\quad 68\quad 89\quad 91\quad 75\quad 77\quad 90\quad 83\)
(end of 3^rd pass): \(53\quad 67\quad 68\quad 72\quad 75\quad 89\quad 91\quad 77\quad 83\quad 90\)
(end of 4^th pass): \(53\quad 67\quad 68\quad 72\quad 75\quad 77\quad 89\quad 91\quad 83\quad 90\)
(end of 5^th pass): \(53\quad 67\quad 68\quad 72\quad 75\quad 77\quad 83\quad 89\quad 91\quad 90\)
(end of 6^th pass): \(53\quad 67\quad 68\quad 72\quad 75\quad 77\quad 83\quad 89\quad 90\quad 91\) (sort complete)

Mark scheme (c)

Scheme	Marks
Pivot 1 = \(\left[\frac{1+20}{2}\right]\) = 11 number 53 68 is after 53 so reject 1 - 11	M1
Pivot 2 = \(\left[\frac{12+20}{2}\right]\) = 16 number 77 68 is before 77 so reject 16 – 20
Pivot 3 = \(\left[\frac{12+15}{2}\right]\) = 14 number 72 68 is before 72 so reject 14 – 15	A1
Pivot 4 = \(\left[\frac{12+13}{2}\right]\) = 13 number 68 – number found	A1(cso)
	(3)
	(11 marks)

Notes

c1M1: Choosing middle right pivot (choosing middle left is M0) + discarding/retaining half the list. So 53 (the 11th value) found as a pivot and either rejecting the first 11or 10 values or retaining the final 9 or 10 values

c1A1: First and second passes correct i.e. 53 found and either using 67 to 91 in 2nd pass or discarding 9 to 53 (so therefore no ‘sticky’ pivots in the first two passes — sticky is when the pivot is retained in the next pass). Then 77 found and either using 67 to 75 in 3rd pass or discarding 77 to 91

c2A1: CSO - search complete + ‘found’ (accept ‘found’, ‘located’, ‘stop’, etc. but not just, for example, the number underlined; must be convinced that 68 has been located and is not a pivot or a number in a sublist with only one value)