Problem

$2.6 \quad 0.8 \quad 2.1 \quad 1.2 \quad 0.9 \quad 1.7 \quad 2.3 \quad 0.3 \quad 1.8 \quad 2.7$

(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5.

The list is to be sorted into descending order.

(b) (i) Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.

(ii) Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes.

After a third pass using this bubble sort, the updated list is

$2.6 \quad 2.1 \quad 1.7 \quad 2.3 \quad 1.2 \quad 1.8 \quad 2.7 \quad 0.9 \quad 0.8 \quad 0.3$

(c) Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.

(d) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5.