東京大学 新領域創成科学研究科 メディカル情報生命専攻 2023年8月実施 問題10

标签：

• Tokyo-University
• Quick-Sort
• Partitioning

Author

zephyr, 祭音Myyura

Description

Given $\mathbf{V}$, an integer array of $N$ elements, the following procedure, quick_sort sorts the entire array of $\mathbf{V}$ by calling quick_sort(0, V, 0, N - 1, -\infty, +\infty). swap(x, y) is a special procedure that swaps the values of $x$ and $y$.

def quick_sort(d, V, li, hi, lv, hv):
    if hi <= li: return
    p = li; l = li + 1; h = hi

	## (A) begins
    while l < h:
        while l <= hi and V[l] < V[p]: l += 1 # (B): V[l] < V[p]
        while li <= h and V[p] <= V[h]: h -= 1 # (C): V[p] <= V[h]
        if h <= l: break
        swap(V[l], V[h])
        l += 1; h -= 1
    swap(V[p], V[h])
    ## (A) ends
    
    if lv < V[h]: quick_sort(d + 1, V, li, l - 1, lv, V[h])
    if V[h] < hv: quick_sort(d + 1, V, h + 1, hi, V[h], hv)

(1) Answer what (A) does over array $\mathbf{V}$.

(2) Answer what $d$ holds.

(3) Let $d_{\max}$ be the maximum $d$ during the entire sorting procedure. Given $N$, show an example of array $\mathbf{V}$ which gives the largest possible $d_{\max}$.

(4) Explain what $lv$ and $hv$ hold.

(5) We modify the program so as to work as is when $d$ is even and as if we swap inequality symbols $(B)$ and $(C)$ when $d$ is odd. Explain what happens if we sort the $\mathbf{V}$ you answered in (3).

(6) Explain the benefits of introducing the modification explained in (5).

---

给定整数数组 $\mathbf{V}$，其包含 $N$ 个元素，以下程序 quick_sort 通过调用 quick_sort(0, V, 0, N - 1, -\infty, +\infty) 对 $\mathbf{V}$ 的整个数组进行排序。swap(x, y) 是一个特殊的过程，用于交换 $x$ 和 $y$ 的值。

def quick_sort(d, V, li, hi, lv, hv):
    if hi <= li: return
    p = li; l = li + 1; h = hi

	// (A) begins
    while l < h:
        while l <= hi and V[l] < V[p]: l += 1
        while li <= h and V[p] <= V[h]: h -= 1
        if h <= l: break
        swap(V[l], V[h])
        l += 1; h -= 1
    swap(V[p], V[h])
    // (A) ends
    
    if lv < V[h]: quick_sort(d + 1, V, li, l - 1, lv, V[h])
    if V[h] < hv: quick_sort(d + 1, V, h + 1, hi, V[h], hv)

(1) 解释 (A) 在数组 $\mathbf{V}$ 上的作用。

(2) 解释 $d$ 的含义。

(3) 设 $d_{\max}$ 为整个排序过程中出现的最大 $d$。给定 $N$，展示一个使得 $d_{\max}$ 最大的数组 $\mathbf{V}$ 的例子。

(4) 解释 $lv$ 和 $hv$ 的含义。

(5) 我们修改程序，以便在 $d$ 为偶数时按原样工作，而在 $d$ 为奇数时交换不等式符号 $(B)$ 和 $(C)$。解释如果我们对 (3) 中的 $\mathbf{V}$ 进行排序会发生什么。

(6) 解释引入 (5) 中修改的好处。

题目描述

给定含 $N$ 个整数的数组 $\mathbf V$，调用

quick_sort(0, V, 0, N - 1, -infinity, +infinity)

执行上文完整的 quick_sort(d, V, li, hi, lv, hv) 程序；swap(x,y) 交换两个变量的值。程序以 V[li] 为枢轴，在代码段 (A) 中用左右游标扫描，其中比较式为：

# (B)
V[l] < V[p]

# (C)
V[p] <= V[h]

随后交换枢轴并对两个子区间作受 lv、hv 条件控制的递归。回答下列问题：

1. 说明代码段 (A) 对数组 $\mathbf V$ 完成了什么操作，并描述结束时枢轴及两侧元素的关系。
2. 说明参数 $d$ 保存的含义。
3. 令 $d_{\max}$ 为整个排序过程中出现的最大 $d$。给定 $N$，构造使 $d_{\max}$ 达到最大可能值的数组 $\mathbf V$。
4. 说明参数 $lv,hv$ 分别保存什么边界信息，以及它们为何用于决定是否递归。
5. 修改程序：$d$ 为偶数时保持原比较方向；$d$ 为奇数时，把 (B)、(C) 中的不等号互换。说明对第 3 问所构造数组排序时，递归与划分会发生什么变化。
6. 说明交替比较方向这一修改的好处。

Kai

Written by zephyr

Caveat. The procedure is not a correct quicksort as printed. For example, on $[1,2]$ the loop is skipped because $l=h$, after which the unconditional swap produces $[2,1]$. On $[0,1,2]$, scan (C) can move $h$ past $p$; Python negative indexing then leads to an infinite recursion, while ordinary pseudocode accesses outside the subarray.

解题思路

这个问题涉及到快速排序算法的深入分析。我们需要理解算法的每个部分，包括分区过程、递归深度、边界条件等。同时，我们还需要分析算法的最坏情况和一个有趣的变体。解答将涉及算法分析、最坏情况构造和算法优化等方面。

1. Analysis of section (A)

Section (A) is intended to be the partitioning step of quicksort. It should perform the following operations on array $\mathbf{V}$:

a) It chooses the first element $V[p]$ as the pivot.

b) It partitions the array such that all elements less than the pivot are moved to the left side, and all elements greater than or equal to the pivot are moved to the right side.

c) Finally, it places the pivot in its correct sorted position.

After a valid partition, the pivot is in its final sorted position, with smaller elements to its left and larger or equal elements to its right. The printed boundary conditions do not guarantee this invariant.

2. The meaning of $d$

$d$ represents the recursion depth of the quicksort algorithm. It starts from 0 and increases by 1 with each recursive call. This parameter can be used to track the depth of the recursion tree or to implement optimizations based on the recursion depth.

3. Worst-case scenario for $d_{\max}$

For the printed procedure there is no largest finite $d_{\max}$. With $\mathbf V=[0,1,2]$, Python semantics alternate the full interval between $[0,1,2]$ and $[2,1,0]$, so $d$ increases without bound. Thus question (3) has no finite answer unless the partition code is corrected. For an ordinary corrected quicksort, a monotone array with distinct keys gives the familiar one-sided recursion.

4. The roles of $lv$ and $hv$

$lv$ and $hv$ are used to optimize the quicksort algorithm by avoiding unnecessary recursive calls:

• $lv$ is the lower value bound inherited by the current subarray.
• $hv$ is the upper value bound inherited by the current subarray.

In the intended partition, values lie between $lv$ and $hv$. After choosing pivot value $V[h]$, a left call is unnecessary when $V[h]=lv$, and a right call is unnecessary when $V[h]=hv$; this is what the two strict tests express.

5. Effect of swapping (B) and (C)

Swapping the inequality symbols exchanges only the treatment of keys equal to the pivot: at even depths they go to the right side, and at odd depths they go to the left side. It does not reverse the sort order. For the distinct-key counterexample $[0,1,2]$ from (3), the comparisons are unchanged, so the printed procedure still does not terminate.

6. Benefit of the modification

For a corrected partition routine, alternating the side that receives keys equal to the pivot prevents a large block of duplicate keys from repeatedly following the same recursive branch. The value-bound tests can then stop that branch earlier, reducing recursion depth and work on duplicate-heavy inputs. It does not repair the boundary errors in the printed code or improve the monotone distinct-key worst case.

Knowledge

难点思路

这道题的难点在于理解快速排序算法的内部工作原理，特别是分区过程和递归结构。另一个挑战是分析算法修改后的行为，这需要深入思考算法在不同情况下的表现。

解题技巧和信息

1. 在分析递归算法时，考虑基本情况和递归情况。
2. 在构造最坏情况输入时，考虑会导致最不平衡分区的情况。
3. 在分析算法优化时，考虑它如何改变算法在不同输入下的行为。

重点词汇

• 快速排序 (Quicksort)
• 分区 (Partitioning)
• 递归深度 (Recursion depth)
• 最坏情况 (Worst-case scenario)
• 轴心元素 (Pivot)
• 时间复杂度 (Time complexity)

参考资料

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms" (Third Edition). MIT Press, 2009. Chapter 7: Quicksort.
2. Robert Sedgewick and Kevin Wayne. "Algorithms" (Fourth Edition). Addison-Wesley Professional, 2011. Chapter 2: Sorting.