Easy -1.8 This is a purely procedural question requiring mechanical execution of standard algorithms (shuttle sort, first-fit decreasing bin packing) with no problem-solving or insight needed. Part (i) is step-by-step algorithm execution, part (ii) is direct application of a named method, and only part (iii) requires minimal trial-and-error thinking. Well below average difficulty for A-level maths.
Use shuttle sort to put this list of values into decreasing order (from largest to smallest).
$$\begin{array} { l l l l l l l l l }
18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22
\end{array}$$
Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.
The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.
Suppose that some stronger boxes are available, each of which can hold at most \(W \mathrm {~kg}\). Find the least value of \(W\) for which only four boxes are needed. Show a packing using four of these stronger boxes.
1 (i) Use shuttle sort to put this list of values into decreasing order (from largest to smallest).
$$\begin{array} { l l l l l l l l l }
18 & 7 & 9 & 20 & 15 & 21 & 6 & 10 & 22
\end{array}$$
Show the result at the end of each pass through the algorithm and write down the number of comparisons and the number of swaps used in each pass.\\
(ii) The values give the weights, in kg , of sacks of grain. The sacks are to be loaded into boxes, each of which can hold at most 30 kg . Use the first-fit decreasing method to show which sacks should be put into which box.\\
(iii) Suppose that some stronger boxes are available, each of which can hold at most $W \mathrm {~kg}$. Find the least value of $W$ for which only four boxes are needed. Show a packing using four of these stronger boxes.
\hfill \mbox{\textit{OCR D1 2013 Q1 [9]}}