(i) 一个包含十二个数字的列表需要按升序排列。

$28 \quad 18 \quad 50 \quad 27 \quad 48 \quad 8 \quad 25 \quad 12 \quad 56 \quad 31 \quad 33 \quad 42$

(a) 使用快速排序获得排序后的列表。应显示每一轮的结果并清楚标明基准元素。

(b) 展示二分搜索算法如何尝试在列表中定位数字 40。必须清楚说明基准元素的选择以及被排除的列表部分。

(ii) 另一个包含九个不同整数的列表需要按降序排列。

$23 \quad 20 \quad x \quad 32 \quad 15 \quad 8 \quad 19 \quad 6 \quad 22$

使用冒泡排序对该列表进行排序。前三轮如下：

确定 $x$ 的可能值范围。

采用官方评分方案中的 middle-right 规则：当子列含偶数个元素时，选中间两个元素中的右侧元素为基准。每一轮把小于基准的元素放在左边、大于基准的元素放在右边，并对尚未排好的子列重复操作。

Using middle-right pivots, begin with pivot 25.

Pass 1:

18  8  12  |25|  28  50  27  48  56  31  33  42

The next pivots are 8 and 56.

Pass 2:

8  18  12  |25|  28  50  27  48  31  33  42  56

The next pivots are 12 and 48.

Pass 3:

8  12  18  |25|  28  27  31  33  42  48  50  56

The nontrivial next pivot is 31; the one-element partitions 18 and 50 are already sorted.

Pass 4:

8  12  18  |25|  28  27  |31|  33  42  48  50  56

The remaining pivots are 27 and 42.

Pass 5:

8  12  18  25  27  28  31  33  42  48  50  56

Therefore, the sorted list is

也可采用官方认可的 middle-left 规则：偶数长度子列选中间左项。只要后续所有子列始终使用同一规则，也会得到相同的升序结果。

Using middle-left pivots, begin with pivot 8.

Pass 1:

8  28  18  50  27  48  25  12  56  31  33  42

The next pivot is 25.

Pass 2:

8  18  12  |25|  28  50  27  48  56  31  33  42

The next pivots are 18 and 48.

Pass 3:

8  12  18  |25|  28  27  31  33  42  48  50  56

The nontrivial next pivots are 31 and 50; the one-element partition 12 is already sorted.

Pass 4:

8  12  18  |25|  28  27  |31|  33  42  48  50  56

The remaining pivots are 28 and 33; the one-element partition 56 is already sorted.

Pass 5:

8  12  18  25  27  28  31  33  42  48  50  56

Hence the sorted list is

在 12 个元素的升序列表中使用 middle-right 基准。每次比较 40 与基准，连同基准本身一起舍弃不可能包含 40 的那一侧，直到只剩一个元素。

Start with the sorted list and choose the middle-right pivot, 31.

8  12  18  25  27  28  |31|  33  42  48  50  56

Since $31<40$, discard 31 and all values below it. The remaining list is

33  42  48  50  56

Choose pivot 48. Since $48>40$, discard 48 and all values above it, leaving

33  42

Choose the middle-right pivot, 42. Since $42>40$, discard 42, leaving

33

Finally, $33\ne40$. Therefore,

降序冒泡排序从左向右比较相邻元素。第一轮中 $x$ 保持在 32 与 15 之间，说明它不会与 15 交换，因此 $x>15$。第三轮中 19 移到 $x$ 前面，说明比较 $x$ 与 19 时发生交换，因此 $x<19$。结合 $x$ 为整数且所有整数互不相同即可得到范围。

From the first pass, $x$ is not swapped with 15, so

From the third pass, 19 is swapped ahead of $x$, so

Therefore,

Since $x$ is an integer, the possible values are