Skip to content

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

Author

zephyr

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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\) 的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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) 中修改的好处。

Kai

Written by zephyr

解题思路

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

1. Analysis of section (A)

Section (A) is the partitioning process of the quicksort algorithm. It performs 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 this process, the pivot element is in its final sorted position, with smaller elements to its left and larger or equal elements to its right.

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}\)

The worst-case scenario for \(d_{\max}\) occurs when the pivot selection consistently results in the most unbalanced partition possible. This happens when the array is already sorted (either in ascending or descending order), and we always choose the first (or last) element as the pivot.

For example, given \(N\), an array \(\mathbf{V}\) that would give the largest possible \(d_{\max}\) is:

\[\mathbf{V} = [1, 2, 3, …, N-1, N]\]

or

\[\mathbf{V} = [N, N-1, N-2, …, 2, 1]\]

In this case, \(d_{\max} = N - 1\), as the recursion will proceed \(N-1\) times before reaching the base case.

4. The roles of \(lv\) and \(hv\)

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

  • \(lv\) (lower value) represents the smallest possible value that could be in the current subarray.
  • \(hv\) (higher value) represents the largest possible value that could be in the current subarray.

These parameters help to avoid unnecessary recursive calls when all elements in a subarray are known to be within a certain range. If \(V[h] \leq lv\) or \(hv \leq V[h]\), we know that all elements in the subarray are already in their correct positions relative to the rest of the array, so we can skip the recursive call.

5. 6. 快速排序算法修改的分析

修改回顾

原始快速排序算法在递归过程中使用相同的分区逻辑。而修改后的版本试图在奇数深度和偶数深度交替使用不同的分区逻辑：

  • 偶数深度：保持原有的小于枢轴在左，大于等于枢轴在右的逻辑
  • 奇数深度：将大于等于枢轴的元素放在左边，小于枢轴的元素放在右边

实际问题分析

1. 错误的排序结果

最主要的问题是，这个修改会导致算法产生错误的排序结果。

原因：

  • 在不同的递归层次，元素的相对顺序被反复颠倒。
  • 最终结果既不是升序也不是降序，而是一种混乱的状态。

例子：

对于输入 [5, 4, 3, 2, 1]，修改后的算法可能会输出类似 `` 的结果。

2. 栈深度没有优化

与最初的预期相反，这个修改并没有减少递归的栈深度。

原因：

  • 虽然分区逻辑改变，但递归的基本结构没有变化。
  • 每次分区仍然只确定一个元素（枢轴）的最终位置。

结果：

  • 在最坏情况下（如已排序的数组），栈深度仍然可能达到 \(O(n)\)。
  • 没有实现预期的将最坏情况复杂度从 \(O(n^2)\) 降低到 \(O(n \log n)\) 的目标。
3. 性能损失

这个修改不仅没有带来性能提升，反而可能导致性能下降。

原因：

  • 额外的条件检查：每次递归都需要检查深度的奇偶性。
  • 缓存不友好：频繁改变比较和交换的逻辑可能导致更多的缓存缺失。
  • 分支预测困难：处理器的分支预测单元可能难以预测交替变化的比较逻辑。
4. 代码复杂性增加

修改增加了代码的复杂性，而没有带来任何好处。

影响：

  • 可读性下降：代码变得更难理解和维护。
  • 更容易引入 bug：复杂的逻辑增加了出错的可能性。
  • 难以优化：复杂的控制流使得编译器优化变得更加困难。

结论

这个所谓的 " 优化 " 实际上是一个反优化：

  1. 它破坏了算法的正确性，无法产生正确的排序结果。
  2. 没有实现预期的栈深度优化，最坏情况的复杂度仍然是 \(O(n^2)\)。
  3. 可能导致性能下降，因为增加了不必要的复杂性和潜在的缓存问题。
  4. 增加了代码的复杂性，使得算法更难理解、维护和进一步优化。

这个案例很好地说明了，在尝试优化复杂算法时，必须非常谨慎，并且要通过严格的理论分析和实际测试来验证任何修改的有效性。对于快速排序这样的经典算法，通常更好的优化方向是：

  • 使用更智能的枢轴选择策略（如三数取中法）
  • 在小规模子数组上切换到插入排序
  • 使用尾递归优化来减少栈使用
  • 考虑非递归实现或使用显式栈来控制递归深度

这些方法可以在不破坏算法正确性的前提下，有效地改善其平均和最坏情况性能。

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.