2. A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.
- Describe how to carry out the first pass of a bubble sort on the numbers in the list.
- State which number in the list is guaranteed to be in the correct final position after the first pass.
- Write down the maximum number of passes required to sort a list of \(n\) numbers.
- The numbers below are to be sorted into descending order. Use a bubble sort, starting at the left-hand end of the list, to obtain the sorted list. You need only give the state of the list after each pass.
$$\begin{array} { l l l l l l l l l }
11 & 9 & 4 & 13 & 5 & 1 & 7 & 12 & 8
\end{array}$$
- Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 21