| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | November |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.8 This is a highly procedural question requiring mechanical execution of standard algorithms (bubble sort, bin packing) with no problem-solving or insight needed. Part (a) is pure algorithm execution following memorized steps, while parts (b) and (c) are straightforward applications of textbook bin-packing methods to a small dataset. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
6. $\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}$
\begin{enumerate}[label=(\alph*)]
\item The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass.
The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
\item Determine the least number of bins needed.
\item Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q6 [10]}}