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

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

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

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

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

确定 $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,

二分搜索也可以在降序列表中进行。(a) 仍须按题目要求完成升序快速排序；这里仅把已排好的列表倒序后搜索，偶数长度时始终选择中间右项。由于列表降序排列，小于 40 的基准及其右侧数值都可舍弃，大于 40 的基准及其左侧数值都可舍弃。

Reverse the sorted list for this search and choose the middle-right pivot, 28.

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

Since $28<40$, discard 28 and all values to its right, leaving

56  50  48  |42|  33  31

The middle-right pivot is now 42. Since $42>40$, discard 42 and all values to its left, leaving

33  |31|

The middle-right pivot is 31. Since $31<40$, discard 31, 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