6.
$$\begin{array} { l l l l l l l l l l }
30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43
\end{array}$$
The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.
- Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.
The list of numbers above is to be sorted into ascending order.
Starting at the left-hand end of the list, after three passes of the bubble sort, the list is
$$\begin{array} { l l l l l l l l l l }
11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60
\end{array}$$ - Write down the list that results at the end of the fourth pass.
- Write down the number of comparisons and swaps performed during the fourth pass.
The original list of numbers is now to be sorted into descending order.
- Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
- Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.