题目
A list of eleven numbers is to be sorted into descending order.
After one pass, the quick sort algorithm produces the following list
(a) State, with a reason, which number was used as a pivot for the first pass.
(b) Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85.
题目中文翻译
一个包含十一个数字的列表要按降序排序。
经过一次传递后，快速排序算法产生以下列表
(a) 说明哪个数字被用作第一次传递的枢轴，并给出理由。
(b) 从上面列表的左端开始，使用冒泡排序获得完全排序的列表。只需写出每次传递结束时的结果列表。
(c) 对完全排序的列表应用首次适应递减装箱算法，将数字装入大小为 85 的箱子中。
解答
(a)
解法一
思路
展开
快速排序完成一次分割后，枢轴左侧的数都应大于枢轴，右侧的数都应小于枢轴。逐一检查列表可发现，只有 13 同时满足这两个条件。
答题过程
展开
The pivot was
Every number to the left of 13 is greater than 13, and every number to its right is less than 13. No other value in the list has this property.
(b)
解法一
思路
展开
要按降序排列，从列表左端开始依次比较相邻两数；若左数小于右数便交换。每次完整传递会把当前最小的未定位数推到右端。官方评分要求列出第五次传递，即使第五次没有发生交换也不能省略。
答题过程
展开
The lists at the end of successive passes are:
| Pass | List |
|---|---|
| 1 | 33, 17, 25, 23, 28, 21, 14, 13, 9, 10, 6 |
| 2 | 33, 25, 23, 28, 21, 17, 14, 13, 10, 9, 6 |
| 3 | 33, 25, 28, 23, 21, 17, 14, 13, 10, 9, 6 |
| 4 | 33, 28, 25, 23, 21, 17, 14, 13, 10, 9, 6 |
| 5 | 33, 28, 25, 23, 21, 17, 14, 13, 10, 9, 6 |
Hence the fully sorted list is
(c)
解法一
思路
展开
按 (b) 的递减顺序逐个放入数字；每个数字都放进从 Bin 1 开始检查时遇到的第一个仍有足够容量的箱子。记录各箱总和可检查没有超过容量 85。
答题过程
展开
Applying first-fit decreasing gives
| Bin | Contents | Total |
|---|---|---|
| 1 | 33, 28, 23 | 84 |
| 2 | 25, 21, 17, 14, 6 | 83 |
| 3 | 13, 10, 9 | 32 |
Therefore the required packing is