| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2023 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.8 This is a straightforward recall and execution question requiring only mechanical application of standard algorithms (identifying a pivot, performing bubble sort passes, and applying first-fit decreasing). No problem-solving, proof, or novel insight is required—just following learned procedures step-by-step. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03k Sorting: quick sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
2. A list of eleven numbers is to be sorted into descending order.
After one pass, the quick sort algorithm produces the following list
$$\begin{array} { l l l l l l l l l l l }
17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10
\end{array}$$
\begin{enumerate}[label=(\alph*)]
\item State, with a reason, which number was used as a pivot for the first pass.
\item Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
\item Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2023 Q2 [6]}}