Problem 1 (教材习题 7-1)

（Hoare 划分的正确性） 第6讲PPT第6页的 PARTITION 算法并不是其最初的版本。下面给出的是最早由 C.R.Hoare 所设计的划分算法：

1. 试说明 HOARE-PARTITION 在数组 $A = \langle13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21\rangle$ 上的操作过程，并说明在每一次执行第 4 到 13 行 while 循环时数组元素的值和辅助变量的值。

后续的三个问题要求读者仔细论证 HOARE-PARTITION 的正确性。在这里假设子数组 $A[p..r]$ 至少包含 2 个元素，试证明下列问题：

2. 下标 $i$ 和 $j$ 不会使我们访问在子数组 $A[p..r]$ 以外的数组 $A$ 的元素。

3. 当 HOARE-PARTITION 结束时，它返回的值 $j$ 满足 $p \le j < r$ 。

4. 当 HOARE-PARTITION 结束时， $A[p..j]$ 中的每一个元素都小于或等于 $A[j + 1..r]$ 中的元素。

在第6讲PPT第6页的 PARTITION 过程中，主元（原来储存在 $A[r]$ 中）是与它所划分的两个分区分离的。与之对应，在 HOARE-PARTITION 中，主元（原来储存在 $A[p]$ 中）是存在于分区 $A[p..j]$ 或 $A[j+1..r]$ 中的。因为有 $p \le j < r$ ，所以这一划分总是非平凡的。

5. 利用HOARE-PARTITION ，重写 QUICKSORT 算法。

Solution

1. 调用 HOARE-PARTITION($A, 1, 12$) ，过程略，第 4 到 13 行的 while 循环结束后， $x = 13, i = 10, j = 9$ 。

2. 首先，第一次循环开始前，有 $i = p - 1, j = r + 1$ 。第一次循环过程中，根据算法第 5 到 10 行的两个 repeat-until ，由于我们是先执行下标更新，后执行数组访问，第二次循环开始前，一定有 $i \ge p, j\le r$ ，所以第一次循环不会越界。并且，根据算法第 12 到 13 行的判断条件，如果 $i \ge j$ 则循环终止。因此，对于算法第 4 到 13 行的 while 循环，从第二次循环开始，每次迭代之前都会有不变式： $p \le i < j \le r$ ，这可以很容易地证明。

3. 首先， $j \ge p$ 是显然的，这是第 2 问结论的一部分，我们只需要证明 $j < r$ 即可。如果第 4 到 13 行的 while 循环运行了不止一次，那么 $j < r$ 是显然的，因为每次迭代至少会运行一次 $j = j - 1$ 。如果只运行了一次，由于 $A[p] = x$ ，因此第一次迭代一定会 $i = p$ ，迭代停止说明 $j \le i = p < r$ ，这里 $p < r$ 是因为 $|A| \ge 2$ 。

4. 使用循环不变式来证明，不变式为： $A[p..i]$ 中的所有元素都小于等于 $x$ ，$A[j..r]$ 中所有的元素都大于等于 $x$ 。这个不变式不难证明，这里不再赘述。当最后一次迭代结束时， $i \ge j$ ，于是 $A[p..j]$ 中的元素都小于等于 $A[j+1..r]$ 中的元素。其中，如果 $i > j$ ，则 $A[i..j]$ 之间的元素都等于 $x$ ，不过这并不影响最重的结论。

5. 只需要注意 Hoare 划分中主元并没有被单独拎出来就可以了。

Problem 2 (教材习题 7-2)

（针对相同元素值的快速排序） 在第6讲PPT第28页对随机化快速排序的分析中，我们假设输入元素的值是互异的，在本题中，我们将看看如果这一假设不成立会出现什么情况。

1. 如果所有输入元素的值都相同，那么随机化快速排序的运行时间会是多少？

2. PARTITION 过程返回一个数组下标 $q$ ，使得 $A[p..q-1]$ 中的每个元素都小于或等于 $A[q]$ ，而 $A[q+1..r]$ 中的每个元素都大于 $A[q]$ 。请修改 PARTITION 代码来构造一个新的 PARTITION’($A, p, r$)，它排列 $A[p..r]$ 的元素，返回值是两个数组下标 $q$ 和 $t$ ，其中 $p \le q \le t \le r$ ，且有

• $A[q..t]$ 中的所有元素都相等。

• $A[p..q-1]$ 中的每个元素都小于 $A[q]$ 。

• $A[t+1..r]$ 中的每个元素都大于 $A[q]$ 。

与 PARTITION 类似，新构造的 PARTITION’ 的时间复杂度是 $\Theta(r-p)$ 。

3. 将 RANDOMIZED-PARTITION 过程修改为调用 PARTITION’ ，并重新命名为 RANDOMIZED-PARTITION’。请修改 QUICKSORT 的代码构造一个新的 QUICKSORT’(A, p, r) ，它调用 RANDOMIZED-PARTITION’ ，并且只有分区内的元素互不相同的时候才做递归调用。

4. 在 QUICKSORT’ 中，应该如何改变第6讲PPT第28页中的分析方法，从而避免所有元素都是互异的这一假设？

Solution

1. 由于所有的输入元素都是相同的， RANDOMIZED-PARTTION 算法每次都会返回 $q = r$ ，从而快速排序运行时间的递归式为 $T(n) = T(n - 1) + \Theta(n)$ ，因此 $T(n) = \Theta(n^2)$ 。

2. 算法伪代码如下，不难看出其时间复杂度为 $\Theta(r - p)$ 。

3. 算法伪代码如下：

4. 由于我们在 QUICKSORT’ 中并没有对相同的元素进行递归调用，因此 QUICKSORT’ 中的子问题规模不会超过 QUICKSORT ，因此运行时间并不会超过所有元素都互异的情况，即 $\Theta(n\log n)$ 。所以分析 QUICKSORT’ 就不需要再作所有元素都互异的假设了，直接和 QUICKSORT 比较即可。

Problem 3 (教材习题 7-3)

（另一种快速排序的分析方法） 对随机化版本的快速排序算法，还有另一种性能分析方法，这一方法关注每一次单独递归调用的期望运行时间，而不是比较的次数。

1. 证明：给定一个大小为 $n$ 的数组，任何特定元素被选为主元的概率为 $1 / n$ 。利用这一点来定义指示器随机变量 $X_i = I{H_i}$ ，其中事件 $H_i$ 表示“第 $i$ 小的元素被选为主元为事件”， $E[X_i]$ 是什么？

2. 设 $T(n)$ 是一个表示快速排序在一个大小为 $n$ 的数组上运行时间的随机变量，试证明：

$E[T(n)] = E\left[\sum_{q=1}^n X_q(T(q-1) + T(n-q) + \Theta(n))\right]$

3. 证明第2问中的公式可以重写为：

$E[T(n)] = \frac{2}{n}\sum_{q=2}^{n-1}E[T(q)] + \Theta(n)$

4. 证明下面的等式（提示：可以将累加式分成两个部分，一部分是 $k = 2, 3, \cdots, \lceil n/2\rceil - 1$ ，另一部分是 $k = \lceil n / 2\rceil , \cdots , n - 1$ ）。

$\sum_{k=2}^{n-1} k \log k \le \frac{1}{2}n^2\log n - \frac{1}{8}n^2$

5. 利用第 4 问中给出的界来证明：第 3 问中的递归式有解 $E[T(n)] = O(n\log n)$ 。（提示：使用代入法，证明对于某个正常数 $a$ 和足够大的 $n$ ，有 $E[T(n)] \le an\log n$ 。）

Solution

1. 根据 RANDOMIZED-PARTITION 算法（见第6讲PPT第24页）第 2 行，主元是在 $n$ 个元素当中随机选取的，因此 $Pr{H_i} = 1/n$ 。根据引理5.1（见第4讲PPT第10页），有

$E[X_i] = E[I{H_i}] = Pr{H_i} = \frac{1}{n}$

2. 当 $H_q$ 发生时，原本的排序问题被划分为两个规模为 $q - 1$ 和 $n - q$ 的子问题，当然，划分过程需要 $\Theta(n)$ 的时间，此时，期望上，$T(n) = E[T(q - 1) + T(n-q) + \Theta(n)]$ ，其中 $i = 1, 2, \cdots, n$ 。根据数学期望的定义，我们有
   $\begin{aligned}$
   E[T(n)] &= \sum_{q=1}^{n} Pr{H_q}\cdot E[T(q-1) + T(n-q) + \Theta(n)]\
   &= \sum_{q=1}^{n} E[X_q]E[T(q-1) + T(n-q) + \Theta(n)]\
   &= \sum_{q=1}^{n} E[X_q(T(q-1) + T(n-q) + \Theta(n))]\
   &= E\left[\sum_{q=1}^{n} X_q(T(q-1) + T(n-q) + \Theta(n))\right]
   \end{aligned}
   其中，倒数第 2 步使用的是事件的独立性，第 1 步使用的是期望的线性性质。

3. 推导过程如下（其中最后一步是因为 $T(1) = O(1)$ ）：

$\begin{aligned}$
E[T(n)] &= \sum_{q=1}^{n} E[X_q]E[T(q-1) + T(n-q) + \Theta(n)]\
&= \sum_{q=1}^{n} \frac{1}{n}E[T(q-1) + T(n-q) + \Theta(n)]\
&= \Theta(n) + \frac{1}{n} \sum_{q=1}^{n} E[T(q-1)] + E[T(n-q)]\
&= \Theta(n) + \frac{2}{n}\sum_{q=1}^{n} E[T(q-1)]\
&= \frac{2}{n}\sum_{q=2}^{n-1} E[T(q)] + \Theta(n)
\end{aligned}

4. 基本思路是将前一半的 $\log k$ 放缩成 $\log (n/2)$ ，后一半的 $\log k$ 放缩成 $\log n$ 。

$\begin{aligned}$
\sum_{k = 2}^{n - 1} k\log k &= \sum_{k = 2}^{\lceil n/2\rceil - 1}k\log k + \sum_{k = \lceil n/2\rceil}^{n-1} k\log k\
&\le \log(n/2)\sum_{k = 2}^{\lceil n / 2 \rceil - 1} k + \log(n)\sum_{k = \lceil n/2\rceil}^{n-1} k\
&= \log n \sum_{k = 2}^{n - 1} k - \sum_{k = 2}^{\lceil n / 2 \rceil - 1} k\
&= \frac{(2 + n-1)(n-2)}{2}\log n - \frac{(2 + \lceil n / 2 \rceil - 1)(\lceil n / 2 \rceil - 1 - 2)}{2}\
&\le (\frac{n^2}2 - \frac{n}2 - 2)\log n - (\frac{n^2}{8} - \frac{n}{2} - \frac{3}{2})\
&=\frac{1}{2}n^2\log n - \frac{1}{8}n^2 - (\log n - 1) \frac{n}{2} - 2(\log n - \frac{3}{4})\
&\le \frac{1}{2}n^2\log n - \frac{1}{8}n^2
\end{aligned}

5. 假设 $E[T(n)] \le n\log n + \Theta(n)$ ，代入第 3 问中的递归式，有
   $\begin{aligned}$
   E[T(n)] &= \frac{2}{n}\sum_{q=2}^{n-1} E[T(q)] + \Theta(n)\
   &\le \frac{2}{n}\sum_{q=2}^{n-1}(q\log q + \Theta(q)) + \Theta(n)\
   &= \frac{2}{n}\sum_{q=2}^{n-1}q\log q + \Theta(n)\
   &\le \frac{2}{n}(\frac{1}{2}n^2\log n - \frac{1}{8}n^2) + \Theta(n)\
   &= n\log n - \frac{1}{4}n + \Theta(n)\
   &= n\log n + \Theta(n)
   \end{aligned}
   于是， $E[T(n)] = O(n\log n)$ 。