AS June 2023 Q1

EdexcelAS paperCurrent spec4 marksAlgorithms

The list of eleven numbers shown above is to be sorted into descending order.

Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.

Mark scheme

Scheme

Marks

Middle right											Pivot(s)
67	59	46	71	40	48	53	63	45	54	56	48
67	59	71	53	63	54	56	\(\underline{48}\)	46	40	45	53, 40
67	59	71	63	54	56	\(\underline{53}\)	\(\underline{48}\)	46	45	\(\underline{40}\)	63, 45
67	71	\(\underline{63}\)	59	54	56	\(\underline{53}\)	\(\underline{48}\)	46	\(\underline{45}\)	\(\underline{40}\)	71, 54, (46)
\(\underline{71}\)	67	\(\underline{63}\)	59	56	\(\underline{54}\)	\(\underline{53}\)	\(\underline{48}\)	46	\(\underline{45}\)	\(\underline{40}\)	(67), 56
\(\underline{71}\)	67	\(\underline{63}\)	59	\(\underline{56}\)	\(\underline{54}\)	\(\underline{53}\)	\(\underline{48}\)	46	\(\underline{45}\)	\(\underline{40}\)

Middle left											Pivot(s)
67	59	46	71	40	48	53	63	45	54	56	48
67	59	71	53	63	54	56	\(\underline{48}\)	46	40	45	53, 40
67	59	71	63	54	56	\(\underline{53}\)	\(\underline{48}\)	46	45	\(\underline{40}\)	71, 46
\(\underline{71}\)	67	59	63	54	56	\(\underline{53}\)	\(\underline{48}\)	\(\underline{46}\)	45	\(\underline{40}\)	63, (45)
\(\underline{71}\)	67	\(\underline{63}\)	59	54	56	\(\underline{53}\)	\(\underline{48}\)	\(\underline{46}\)	45	\(\underline{40}\)	(67), 54
\(\underline{71}\)	67	\(\underline{63}\)	59	56	\(\underline{54}\)	\(\underline{53}\)	\(\underline{48}\)	\(\underline{46}\)	45	\(\underline{40}\)	59
\(\underline{71}\)	67	\(\underline{63}\)	\(\underline{59}\)	56	\(\underline{54}\)	\(\underline{53}\)	\(\underline{48}\)	\(\underline{46}\)	45	\(\underline{40}\)

M1
A1
A1ft
A1

1.1b
1.1b
1.1b
1.1b

(4)

(4 marks)

Notes

M1: Quick Sort, pivot, p, chosen (must be choosing middle right or middle left). After the first pass the list must read (values greater than the pivot), pivot, (values less than the pivot). If choosing only one pivot per iteration, then M1 only. Their original list of 10, 11 or 12 numbers must be a list of 10, 11 or 12 numbers after the first pass

A1: First two passes correct (pivots for third pass need not be chosen)

A1ft: Third and fourth passes correct (follow through from their second pass and choice of consistent pivots) (pivot(s) for the fifth pass need not be chosen). After their second pass their list must contain either 10, 11 or 12 numbers (so allow one additional/missing number)

A1: cso – if choosing middle right pivots then they must include a fifth pass and if choosing middle left then they must include a sixth pass

SC: If list is sorted into ascending order, then award a maximum of M1A1A0A0 (so 2 marks) as in the scheme above even if the list is re-ordered after the sort is complete

Ascending:

67	59	46	71	40	48	53	63	45	54	56
46	40	45	\(\underline{48}\)	67	59	71	53	63	54	56
\(\underline{40}\)	46	45	\(\underline{48}\)	\(\underline{53}\)	67	59	71	63	54	56