$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) 使用首次适应装箱算法确定上面列出的数字如何装入大小为 5 的箱子中。

列表要按降序排序。

(b) (i) 从上面列表的左端开始，使用冒泡排序对列表执行两次传递。写出第一次传递和第二次传递结束时的结果列表。

(ii) 在答案本的表格中写出这两次传递期间执行的比较次数和交换次数。

使用此冒泡排序进行第三次传递后，更新的列表为

$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) 对此更新的列表使用快速排序获得完全排序的列表。必须清楚标出枢轴。

(d) 对完全排序的列表应用首次适应递减装箱算法，将数字装入大小为 5 的箱子中。

按原列表顺序逐个处理数值。每次从第一个箱子开始检查，把当前数值放入第一个总和不超过 5 的箱子；只有所有已有箱子都放不下时才开启新箱子。

Applying the first-fit bin packing algorithm gives:

Thus the first-fit allocation uses

要按降序排列，从左端开始比较相邻元素；若左边小于右边，就交换两者。第一趟会把最小值移到最右端，第二趟只需处理前九个位置。

After the first pass, the list is

After the second pass, the list is

第一趟需要比较全部 10 个元素之间的 9 对相邻位置。最小值已经就位后，第二趟不再比较最后一个位置，所以比较次数降为 8；交换次数则按每次实际发生的位置交换逐一计数。

采用官方评分资料给出的 middle-right 选枢轴规则。每轮把大于枢轴的元素按原相对顺序放在左边，把小于枢轴的元素放在右边，再对子列表重复操作。每轮都明确列出所选枢轴。

Choose the middle-right item $1.8$ as the first pivot. The first partition is

For the two unsorted sublists, choose pivots $2.3$ and $0.9$. This gives

Next choose pivots $2.7$, $1.2$ and $0.3$ in the remaining non-trivial sublists. The list becomes

Rewriting the unchanged list confirms that the sort is complete:

官方也接受 middle-left 选枢轴规则。分割原则不变，只是偶数长度子列表选取中间两个元素中的左边一个，因此中间状态不同，但最终仍得到同一降序列表。

Choose the middle-left item $1.2$ as the first pivot. The first partition is

Choose pivots $1.7$ and $0.8$ for the two unsorted sublists:

Using $2.3$ as the next non-trivial pivot gives

Finally choose pivots $2.6$ and $2.1$. The fully sorted list is

Rewriting this unchanged list confirms that the sort is complete.

使用 (c) 的完整降序列表，依次对每个数应用首次适应规则。每个数仍须从第一个箱子开始尝试，而不是直接放入当前最后一个箱子。

Applying first-fit decreasing to the sorted list gives:

Thus the first-fit decreasing allocation uses