| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2021 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bin Capacity Constraints |
| Difficulty | Moderate -0.8 This is a straightforward application of standard algorithms (quick sort and bin packing) with clear step-by-step procedures. Part (a) requires mechanical execution of quick sort, part (b) involves simple logical deduction from given constraints (finding n such that 36 fits but certain sums don't exceed n), and part (c) applies first-fit decreasing algorithmically. No novel problem-solving or deep insight required—purely procedural with multiple marks for showing working. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Bin 1: | 30 | 12 | 2 |
| Bin 2: | 5 | 23 | 10 |
| Bin 3: | 18 | 15 | |
| Bin 4: | 36 | ||
| Bin 5: | 24 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Quick sort, middle right pivot(s): 30, 12, 5, 2, 23, 18, 36, 10, 15, 24 | M1 | Pivot chosen must be middle left or right. Choosing first/last item is M0. After first pass list must read (values \(>\) pivot), pivot, (values \(<\) pivot). If only one pivot per iteration: max M1 only. Bubble sort scores M0 |
| 30, 23, 36, 24, 18, 12, 5, 2, 10, 15 (first pass correct and next pivots correctly chosen for second pass) | A1 | Second pass does not need to be correct |
| \(\underline{36}\), 30, 23, 24, 18, 12, 5, 10, 15, \(\underline{2}\) | A1ft | Second and third passes correct (follow through from first pass and pivot choices) |
| \(\underline{36}\), 30, 24, 23, 18, 15, 12, 10, 5, \(\underline{2}\) | — | — |
| \(\underline{36}\), 30, 24, 23, 18, 15, 12, 10, 5, \(\underline{2}\); sort is complete | A1 | cso – all previous marks must have been awarded, including 'sort complete' statement. If sorted into ascending order, mark as MR |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| 5 placed in Bin 2 rather than Bin 1 indicates bin size \(< 30+12+5=47\), therefore \(42 \leq n \leq 46\) | B1 | — |
| Room for 2 in Bin 1 indicates \(n \geq 44\) | B1 | — |
| 18 cannot fit in Bin 2 therefore \(n < 5+23+18=46\), implying \(n\) is either 44 or 45 | B1 | — |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Bin 1: 36, 5, 2; Bin 2: 30, 15; Bin 3: 24, 18; Bin 4: 23, 12, 10 | M1 | — |
| — | A1 | — |
| — | A1 | — |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct reasoning why \(n \leq 46\) or \(n < 47\) or \(n \leq 45\) or \(n < 46\), e.g. \(n < 30 + 12 + 5\) or \(n < 5 + 23 + 18\) | B1 | Condone mathematical argument only |
| Correct reasoning why \(n \geq 44\), e.g. 'largest bin filled is 44 so \(n \geq 44\)', e.g. \(n \geq 30 + 12 + 2\) | B1 | Condone mathematical argument only |
| Completely correct reasoning for why \(n\) is either 44 or 45 only | B1 | Dependent on previous two B marks; must give sufficient detail |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| First five values placed correctly with at least eight values placed (the squared values) | M1 | No MR or follow through in this part |
| First eight values placed correctly with no additional/repeated values (squared and underlined values) | A1 | |
| Final sorted list correct, no additional/repeated values | A1 | cso |
| Answer | Marks | Guidance |
|---|---|---|
| 30 | 12 | 5 |
| 30 | 36 | 24 |
| <u>36</u> | 30 | 24 |
| <u>36</u> | <u>30</u> | 24 |
| <u>36</u> | <u>30</u> | 24 |
| <u>36</u> | <u>30</u> | 24 |
| <u>36</u> | <u>30</u> | 24 |
# Question 5:
**(a)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Quick sort, middle right pivot(s): 30, 12, 5, 2, 23, **18**, 36, 10, 15, 24 | M1 | Pivot chosen must be middle left or right. Choosing first/last item is M0. After first pass list must read (values $>$ pivot), pivot, (values $<$ pivot). If only one pivot per iteration: max M1 only. Bubble sort scores M0 |
| 30, 23, **36**, 24, **18**, 12, 5, **2**, 10, 15 (first pass correct and next pivots correctly chosen for second pass) | A1 | Second pass does not need to be correct |
| $\underline{36}$, 30, **23**, 24, **18**, 12, 5, **10**, 15, $\underline{2}$ | A1ft | Second and third passes correct (follow through from first pass and pivot choices) |
| $\underline{36}$, 30, **24**, **23**, **18**, **15**, 12, **10**, 5, $\underline{2}$ | — | — |
| $\underline{36}$, 30, 24, 23, 18, 15, 12, 10, 5, $\underline{2}$; sort is complete | A1 | cso – all previous marks must have been awarded, including 'sort complete' statement. **If sorted into ascending order, mark as MR** |
**(b)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| 5 placed in Bin 2 rather than Bin 1 indicates bin size $< 30+12+5=47$, therefore $42 \leq n \leq 46$ | B1 | — |
| Room for 2 in Bin 1 indicates $n \geq 44$ | B1 | — |
| 18 cannot fit in Bin 2 therefore $n < 5+23+18=46$, implying $n$ is either 44 or 45 | B1 | — |
**(c)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Bin 1: 36, 5, 2; Bin 2: 30, 15; Bin 3: 24, 18; Bin 4: 23, 12, 10 | M1 | — |
| — | A1 | — |
| — | A1 | — |
# Question 5(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct reasoning why $n \leq 46$ or $n < 47$ or $n \leq 45$ or $n < 46$, e.g. $n < 30 + 12 + 5$ or $n < 5 + 23 + 18$ | B1 | Condone mathematical argument only |
| Correct reasoning why $n \geq 44$, e.g. 'largest bin filled is 44 so $n \geq 44$', e.g. $n \geq 30 + 12 + 2$ | B1 | Condone mathematical argument only |
| Completely correct reasoning for why $n$ is either 44 or 45 only | B1 | Dependent on previous two B marks; must give sufficient detail |
# Question 5(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| First five values placed correctly with at least eight values placed (the squared values) | M1 | No MR or follow through in this part |
| First eight values placed correctly with no additional/repeated values (squared and underlined values) | A1 | |
| Final sorted list correct, no additional/repeated values | A1 | cso |
**Middle left pivot(s) working:**
| 30 | 12 | 5 | 2 | **23** | 18 | 36 | 10 | 15 | 24 |
| 30 | **36** | 24 | <u>23</u> | 12 | 5 | **2** | 18 | 10 | 15 |
| <u>36</u> | **30** | 24 | <u>23</u> | 12 | 5 | **18** | 10 | 15 | <u>2</u> |
| <u>36</u> | <u>30</u> | 24 | <u>23</u> | <u>18</u> | 12 | **5** | 10 | 15 | <u>2</u> |
| <u>36</u> | <u>30</u> | 24 | <u>23</u> | <u>18</u> | 12 | **10** | 15 | <u>5</u> | <u>2</u> |
| <u>36</u> | <u>30</u> | 24 | <u>23</u> | <u>18</u> | **12** | 15 | <u>10</u> | <u>5</u> | <u>2</u> |
| <u>36</u> | <u>30</u> | 24 | <u>23</u> | <u>18</u> | 15 | <u>12</u> | <u>10</u> | <u>5</u> | <u>2</u> |
---\begin{enumerate}
\item 30312522318136101524\\
(a) The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\end{enumerate}
The ten numbers are to be packed into bins of size $n$, where $n$ is a positive integer.\\
When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.
\begin{center}
\begin{tabular}{ l r r r }
Bin 1: & 30 & 12 & 2 \\
Bin 2: & 5 & 23 & 10 \\
Bin 3: & 18 & 15 & \\
Bin 4: & 36 & & \\
Bin 5: & 24 & & \\
\end{tabular}
\end{center}
(b) Explain why the value of the integer $n$ must be either 44 or 45\\
(c) Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45\\
\hfill \mbox{\textit{Edexcel FD1 2021 Q5 [10]}}