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

列表要按降序排序。

(b) (i) 从列表左端开始执行一次冒泡排序传递。必须写出第一次传递结束时的结果列表。

(ii) 写出第一次传递期间执行的比较次数和交换次数。

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

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

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

按题目给出的原始顺序逐个处理数字。每个数字都从 Bin 1 开始检查，放入第一个剩余容量足够的箱子；只有现有箱子都放不下时才开新箱。

Applying first-fit bin packing gives

要按降序排列，从左端开始比较每一对相邻数字；若左数小于右数就交换。完成一次从左至右的传递后，当前最小值 0.6 会被推到最右端。

After one complete pass, the list is

十一个数字的一次完整冒泡传递会比较十对相邻数字。逐次追踪 (b)(i) 的交换，可数得其中六次需要交换。

The first pass uses

采用 middle-right 规则：每个尚未排好的子列表都选择中间两个元素中靠右的一个作为枢轴。每轮把大于枢轴的数放在左侧、小于枢轴的数放在右侧，并对各子列表继续使用同一规则。即使第四轮后列表已排序，仍要写出第五轮。

Using middle-right pivots gives:

Hence the fully sorted list is

也可采用官方接受的 middle-left 规则，即每个偶数长度子列表选择中间靠左的元素作为枢轴。必须在所有子列表中一致使用这一规则，并把最后一次无变化的传递写出。

Using middle-left pivots gives:

Therefore the same fully sorted list is obtained:

按 (c) 的递减顺序逐个放入数字，并对每个数字从 Bin 1 开始寻找第一个可容纳它的箱子。这与 (a) 的 first-fit 规则相同，差别只在于先按递减顺序排序。

Applying first-fit decreasing gives