| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2024 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Moderate -0.8 This is a routine D1 question testing standard algorithm execution. Part (a) requires simple arithmetic to find bin capacity constraints, part (b) is mechanical quick sort execution following a learned procedure, and part (c) is straightforward deduction. No problem-solving insight needed, just careful application of textbook algorithms. |
| Spec | 7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 28 | 31 | 5 | 25 | 16 | 35 | 18 | 22 | 11 | 27 | 15 | 13 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Bin 3 has the largest sum of the four bins with \(72 \Rightarrow n \geqslant 72\) | B1 | Correct reasoning why \(n\) is at least 72; states or shows a bin (3) has total 72 and concludes this is the least value |
| After the first three numbers were placed in Bin 1 (with a total of 64) the next smallest value (the 11) could not fit in Bin \(1 \Rightarrow n < 64 + 11\) | B1 | Correct reasoning regarding upper bound for \(n\) – that as the second smallest value (the 11) was not put in Bin 1 then \(n <\) the sum of Bin \(1 + 11\) |
| \(72 \leqslant n \leqslant 74\), e.g. \(n = 72, 73\) or \(74\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| First pass with pivot 18 (middle right): \(28,31,5,25,16,\underline{35},18,22,11,27,15,13\) | M1 | Quick sort – pivots, \(p\), selected and first pass gives \( |
| Correct first pass and next pivots chosen correctly/consistently for second pass | A1 | |
| Second and third passes correct (ft from their first pass and choice of pivots) | A1ft | |
| CSO including a fifth pass: \(5,11,13,15,16,18,22,25,27,28,31,35\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| After the 27 has been placed in Bin 2 (giving a total of 55) the 18 was placed in Bin 3 not Bin 2 indicating that \(n < 55 + 18\) | B1 | Correct reasoning regarding placement of 18 in Bin 3 rather than Bin 2 (must explicitly mention 18) |
| \(n = 72\) | dB1 | Dependent on previous B mark – CAO (\(n=72\)) |
## Question 6(a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Bin 3 has the largest sum of the four bins with $72 \Rightarrow n \geqslant 72$ | B1 | Correct reasoning why $n$ is at least 72; states or shows a bin (3) has total 72 and concludes this is the least value |
| After the first three numbers were placed in Bin 1 (with a total of 64) the next smallest value (the 11) could not fit in Bin $1 \Rightarrow n < 64 + 11$ | B1 | Correct reasoning regarding upper bound for $n$ – that as the second smallest value (the 11) was not put in Bin 1 then $n <$ the sum of Bin $1 + 11$ |
| $72 \leqslant n \leqslant 74$, e.g. $n = 72, 73$ or $74$ | B1 | |
---
## Question 6(b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| First pass with pivot 18 (middle right): $28,31,5,25,16,\underline{35},18,22,11,27,15,13$ | M1 | Quick sort – pivots, $p$, selected and first pass gives $<p, p, >p$. If only choosing 1 pivot per iteration M1 only. If sorting into descending order then mark as misread |
| Correct first pass and next pivots chosen correctly/consistently for second pass | A1 | |
| Second and third passes correct (ft from their first pass and choice of pivots) | A1ft | |
| CSO including a fifth pass: $5,11,13,15,16,18,22,25,27,28,31,35$ | A1 | |
---
## Question 6(c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| After the 27 has been placed in Bin 2 (giving a total of 55) the 18 was placed in Bin 3 not Bin 2 indicating that $n < 55 + 18$ | B1 | Correct reasoning regarding placement of 18 in Bin 3 rather than Bin 2 (must explicitly mention 18) |
| $n = 72$ | dB1 | Dependent on previous B mark – CAO ($n=72$) |
---6. The twelve numbers in the list below are to be packed into bins of size $n$, where $n$ is a positive integer.
\begin{center}
\begin{tabular}{ l l l l l l l l l l l l l }
28 & 31 & 5 & 25 & 16 & 35 & 18 & 22 & 11 & 27 & 15 & 13 \\
\end{tabular}
\end{center}
When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained.
Bin 1: 28315\\
Bin 2: 25161811\\
Bin 3: 352215\\
Bin 4: 2713
\begin{enumerate}[label=(\alph*)]
\item Based on the packing shown above, determine the possible values of $n$. You must give reasons for your answer.
\item The original list of twelve numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained.
Bin 1: 35315\\
Bin 2: 282716\\
Bin 3: 252218\\
Bin 4: 151311
\item Determine the value of $n$. You must give a reason for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2024 Q6 [9]}}