Problem

$1.8 \quad 1.4 \quad 2.6 \quad 1.6 \quad 2.8 \quad 0.9 \quad 3.1 \quad 0.8 \quad 1.2 \quad 2.4 \quad 0.6$

(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) Perform one pass of a bubble sort, starting at the left-hand end of the list. You must write down the list that results at the end of the first pass.

(ii) Write down the number of comparisons and the number of swaps performed during the first pass.

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

$2.6 \quad 1.8 \quad 2.8 \quad 1.6 \quad 3.1 \quad 1.4 \quad 1.2 \quad 2.4 \quad 0.9 \quad 0.8 \quad 0.6$

(c) Use a quick sort on this updated list to obtain the fully sorted list in descending order. 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.