| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2022 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.8 This is a routine D1 question requiring mechanical application of standard algorithms (bubble sort and first-fit decreasing) with no problem-solving or insight needed. The lower bound calculation is a simple sum divided by capacity, and executing bubble sort/bin packing are purely procedural tasks following memorized steps. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
\begin{enumerate}
\item $\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}$
\end{enumerate}
The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .\\
(a) Calculate a lower bound for the number of trucks that will be needed to transport the crates.\\
(b) Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.\\
(c) Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.\\
\hfill \mbox{\textit{Edexcel D1 2022 Q1 [9]}}