A2 June 2019 Q1

EdexcelCurrent spec8 marksAlgorithms

2.1

1.7

3.0

1.9

3.2

1.2

3.3

1.4

1.5

0.2

(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 (2)

The list of numbers is now to be sorted into descending order.

(b) Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. (4)

For a list of \(n\) numbers, the quick sort algorithm has, on average, order \(n\log n\).

Given that it takes 2.32 seconds to run the algorithm when \(n = 450\)

(c) calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when \(n = 11\,250\). You should make your method and working clear. (2)

Mark scheme (a)

Scheme	Marks	AO
Bin 1: 2.1 1.7 1.2 Bin 2: 3.0 1.9 Bin 3: 3.2 1.4 0.2 Bin 4: 3.3 1.5	M1 A1	1.1b 1.1b
	(2)

Notes

PLEASE NOTE NO MISREADS IN PARTS (a) and (b) – MARK ACCORDING TO THE SCHEME AND THE SPECIAL CASE FOR ASCENDING ORDER IN (b)

(a) M1: First six items placed correctly and at least eight values placed in bins - condone cumulative totals for M1 only (the underlined values)

A1: CSO – all correct (so no additional/repeated values)

Mark scheme (b)

Scheme

Marks

e.g. middle right

2.1	1.7	3.0	1.9	3.2	\(\boxed{1.2}\)	3.3	1.4	1.5	0.2	Pivot: 1.2
2.1	1.7	3.0	1.9	\(\boxed{3.2}\)	3.3	1.4	1.5	\(\underline{1.2}\)	0.2	Pivot(s): 3.2 (0.2)
3.3	\(\underline{3.2}\)	2.1	1.7	3.0	\(\boxed{1.9}\)	1.4	1.5	\(\underline{1.2}\)	0.2	Pivot(s): (3.3) 1.9
3.3	\(\underline{3.2}\)	2.1	\(\boxed{3.0}\)	\(\underline{1.9}\)	1.7	\(\boxed{1.4}\)	1.5	\(\underline{1.2}\)	0.2	Pivots: 3.0 1.4
3.3	\(\underline{3.2}\)	\(\underline{3.0}\)	2.1	\(\underline{1.9}\)	1.7	\(\boxed{1.5}\)	\(\underline{1.4}\)	\(\underline{1.2}\)	0.2	Pivot(s): (2.1) 1.5
3.3	\(\underline{3.2}\)	\(\underline{3.0}\)	2.1	\(\underline{1.9}\)	1.7	\(\underline{1.5}\)	\(\underline{1.4}\)	\(\underline{1.2}\)	0.2

M1

A1
A1ft
A1

1.1b

1.1b
1.1b
1.1b

(4)

Notes

(b) M1: 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 max of M1A1 only – Bubble sort is not a MR and scores M0

A1: First pass correct and next pivots chosen correctly for the second pass (but the second pass does not need to be correct) – so they must be choosing (if middle right) a pivot value of 3.2 for the second pass or (if middle left) a pivot value of 1.9

A1ft: 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

A1: CSO (correct solution only – all previous marks in this part must have been awarded) including if middle right a fifth pass with the 1.5 used as a pivot or if middle left a fourth pass with the 1.7 used as a pivot

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 remove the last two A marks earned in (b). If the candidate says that the list needs reversing in (b) but does not actually show the reversed list in (b) then remove the last A mark earned
Note that if sorting into ascending order then a ‘sort complete’ statement is required – 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) BEFORE list is reversed

Middle left

2.1	1.7	3.0	1.9	\(\boxed{3.2}\)	1.2	3.3	1.4	1.5	0.2
3.3	\(\underline{3.2}\)	2.1	1.7	3.0	\(\boxed{1.9}\)	1.2	1.4	1.5	0.2
3.3	\(\underline{3.2}\)	\(\boxed{2.1}\)	3.0	\(\underline{1.9}\)	1.7	1.2	\(\boxed{1.4}\)	1.5	0.2
3.3	\(\underline{3.2}\)	3.0	\(\underline{2.1}\)	\(\underline{1.9}\)	\(\boxed{1.7}\)	1.5	\(\underline{1.4}\)	\(\boxed{1.2}\)	0.2
3.3	\(\underline{3.2}\)	3.0	\(\underline{2.1}\)	\(\underline{1.9}\)	\(\underline{1.7}\)	1.5	\(\underline{1.4}\)	\(\underline{1.2}\)	0.2

Middle right ascending (which requires a ‘sort complete’ statement – see above)

2.1	1.7	3.0	1.9	3.2	\(\boxed{1.2}\)	3.3	1.4	1.5	0.2
0.2	\(\underline{1.2}\)	2.1	1.7	3.0	1.9	\(\boxed{3.2}\)	3.3	1.4	1.5
0.2	\(\underline{1.2}\)	2.1	1.7	3.0	\(\boxed{1.9}\)	1.4	1.5	\(\underline{3.2}\)	3.3
0.2	\(\underline{1.2}\)	1.7	\(\boxed{1.4}\)	1.5	\(\underline{1.9}\)	2.1	\(\boxed{3.0}\)	\(\underline{3.2}\)	3.3
0.2	\(\underline{1.2}\)	\(\underline{1.4}\)	1.7	\(\boxed{1.5}\)	\(\underline{1.9}\)	2.1	\(\underline{3.0}\)	\(\underline{3.2}\)	3.3
0.2	\(\underline{1.2}\)	\(\underline{1.4}\)	\(\underline{1.5}\)	1.7	\(\underline{1.9}\)	2.1	\(\underline{3.0}\)	\(\underline{3.2}\)	3.3

Middle left ascending (which required a ‘sort complete’ statement – see above)

2.1	1.7	3.0	1.9	\(\boxed{3.2}\)	1.2	3.3	1.4	1.5	0.2
2.1	1.7	3.0	\(\boxed{1.9}\)	1.2	1.4	1.5	0.2	\(\underline{3.2}\)	3.3
1.7	1.2	\(\boxed{1.4}\)	1.5	0.2	\(\underline{1.9}\)	\(\boxed{2.1}\)	3.0	\(\underline{3.2}\)	3.3
\(\boxed{1.2}\)	0.2	\(\underline{1.4}\)	\(\boxed{1.7}\)	1.5	\(\underline{1.9}\)	\(\underline{2.1}\)	3.0	\(\underline{3.2}\)	3.3
0.2	\(\underline{1.2}\)	\(\underline{1.4}\)	1.5	\(\underline{1.7}\)	\(\underline{1.9}\)	\(\underline{2.1}\)	3.0	\(\underline{3.2}\)	3.3

Mark scheme (c)

Scheme	Marks	AO
\(\dfrac{2.32\,(11\,250\log 11\,250)}{450\log 450}\)	M1	1.1a
= 88.6 seconds	A1	1.1b
	(2)
	(8 marks)

Notes

(c) M1: Complete correct method – allow reciprocal – allow slips in values only e.g. 1250 for 11 250

A1: CAO – the exact value of 88.6 must be stated at some point (as question specifically asked for the answer to the nearest tenth of a second) – isw if 90 follows 88.6 seen. 90 with no working scores no marks. An answer of 88.6 with no working scores M1A0 – condone lack of units (but if present must be correct)