Problem

(a) (i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of $n$ numbers into ascending order.

(ii) Write down the circumstances under which a bubble sort stops.

A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads:

$0.9 \quad 1.2 \quad 1.5 \quad 0.5 \quad 1.4 \quad 1.1 \quad 0.7 \quad 1.7 \quad 2.2 \quad 3.2$

(b) Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.

(c) Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.

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