Problem

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

(ii) Write down the circumstances under which the 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:

$\_\_ \quad \_\_ \quad 12 \quad 15 \quad \_\_ \quad \_\_ \quad \_\_ \quad \_\_ \quad D8$

(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.

(Total 13 marks)