3.2 Selection、quickselect 與 linear-time sorting

選擇問題只要求一個指定排名的元素，排序卻要給出全部元素的完整次序。這個區別使 quickselect 可以捨棄不會影響目標排名的工作。Counting sort 與 LSD radix sort 更進一步：它們利用 key 的額外結構跨過比較排序下界，但必須清楚說明值域、位數與計算模型。

動機

假設一個 list 有數百萬個值，而我們只需要中位數。先完整排序當然能夠得到答案，可是完整次序所含的資訊遠多於一個中位數。選擇演算法之前，先確認題目實際要求甚麼 output，是重要的演算法設計習慣。

倉庫內的 tutorial 依次給出三層思路。完整排序是容易理解的基線；partial selection sort 只放好最前面的若干 order statistics；quickselect 重用 quicksort 的 partition，但只進入可能包含目標的一邊。其後，linear-time sorting 講義改變計算模型：有界整數可以直接計數，多位 key 則可以逐位穩定排序。

本節處理的是靜態、單次查詢。若資料不更新而要查詢很多個排名，先排序一次可能合理；若查詢之間還會頻繁插入和刪除，dynamic selection tutorial 指向維護 subtree size 的高度平衡搜尋樹。它的對數保證依賴平衡性和 metadata 的正確維護，所以完整實作應放在 tree notes；這裏只交代靜態選擇與 dynamic order statistics 的邊界。

定義

選擇問題

給定含 $n$ 個 key 的 list $A$ ，以及滿足 $1 \le k \le n$ 的整數 $k$ ，返回 第 $k$ 小的 key。排名採用 1-based，偽代碼中的 array index 可以採用 0-based。重複值按出現次數分別計入：在 $[2,2,5]$ 中，第 1 小和第 2 小都是 $2$ 。

$k=1$ 與 $k=n$ 分別是 minimum 與 maximum，只需一次掃描，所以 comparison model 下的 selection 並不存在一般性的 $\Omega(n\log n)$ 下界。後文的下界針對輸出完整次序的排序，而不是只找一個排名。

Partial selection sort 執行 selection sort 的前 $k$ 輪。第 $i$ 輪找出剩餘 suffix 的最小值，與位置 $i$ 交換，最後返回 A[k - 1]；array 實作無需真的刪除元素。比較次數恰好是

\sum_{i=0}^{k-1}(n-i-1) =k(n-1)-\frac{k(k-1)}2,

所以是 $O(kn)$ 。固定常數 $k$ 時為線性；當 $k=\Theta(n)$ 時則為二次。

定義

Partition 契約

對長度為 $m$ 的目前 subarray，Partition 返回 index $p$ ，把 pivot 放在 A[p]，並保證 $p$ 左邊每個 key 都不大於 A[p]，右邊每個 key 都不小於 A[p]。因此即使有重複值，pivot value 也是局部第 $p+1$ 小的一個合法值。這個「pivot 最終 index」契約比只返回兩個區域邊界的 partition 更強。

若 $k$ 是相對於目前 subarray 的 1-based rank，正確分支結構是：

Quickselect(A, m, k):
    require 1 ≤ k ≤ m
    if m == 1: return A[0]
    p = Partition(A, m)          // p 是 pivot 最終的 0-based index
    if k - 1 == p: return A[p]
    if k - 1 is below p: return Quickselect(A[0:p], p, k)
    return Quickselect(A[p+1:m], m-p-1, k-p-1)

相等分支不可省略。進入右邊時，新 rank 要減去左邊的 $p$ 個位置和 pivot 本身。

每次 recursive call 開始時都保持這個 invariant：目前 subarray 含有原題所求的 order statistic，而參數 $k$ 是它在目前 subarray 內的 rank。左邊 call 沒有丟棄任何更小位置，所以保留 $k$ ；右邊 call 恰好丟棄 $p+1$ 個位置，所以使用 $k-p-1$ 。Equality return 在 pivot 處停止，而且兩個 recursive branches 都嚴格短於 parent，因此 base case 必會到達。若 partition 返回的是 Hoare-style boundary 而不是 pivot 最終 index，就需要另一套論證，不能原樣代入這段 pseudocode。

Randomized three-way quickselect

上面的 source teaching trace 使用 two-way final-index partition。若 input 可能有 duplicates，而我們要證明 expected-time guarantee，應另用 three-way variant：從目前 records 中 uniform random 選一個 pivot，再分成 strict-less block $L$ 、equal block $E$ 與 strict-greater block $G$ 。令 $k$ 是 1-based local rank， $\ell=|L|$ 、 $e=|E|$ ：

RandomizedQuickselect(A, m, k):
    pivot = key of a uniformly random record in A
    (L, E, G) = ThreeWayPartition(A, pivot)
    if k ≤ |L|:       return RandomizedQuickselect(L, |L|, k)
    if k ≤ |L| + |E|: return pivot
    return RandomizedQuickselect(G, |G|, k-|L|-|E|)

這裏保持同一個 recursive-call invariant，但 greater branch 丟棄的 prefix 大小變成 $\ell+e$ 。每次 recursive call 都只進入 strict block，所以規模嚴格縮小；若所有 keys 相等， $E$ 就是整個 input，algorithm 做一次 $\Theta(m)$ partition 後直接 return。這個 three-way contract 也不同於 Hoare boundary，必須按自身語義實作和證明。

定義

穩定排序

若具有相同 key 的 records 在 output 中保持 input 的相對次序，sorting routine 就是 stable。當後續 pass 按 compound key 的另一部分排序，而又必須保留較早 pass 建立的次序時，stability 是正確性條件。

定義

Counting sort

若整數 key 落在 inclusive range $0,1,\ldots,K$ ，標準 stable counting sort 需要 $K+1$ 個 counters。它先統計頻率，再求 prefix counts，最後從右到左掃描 input，把 records 放入獨立 output array。時間為 $\Theta(n+K)$ ；若同時計算 output 與 count arrays，auxiliary space 為 $\Theta(n+K)$ 。這個標準 stable 版本不是 in-place。

定義

LSD radix sort

設每個非負 key 在 base $b$ 下有 $d$ 位。Least-significant-digit (LSD) radix sort 先對 digit $0$ 做 stable sort，再處理 digit $1$ ，直至 digit $d-1$ 。若每一輪用 counting sort 處理 $b$ 種 digit value，總時間為 $\Theta(d(n+b))$ ，auxiliary space 為 $\Theta(n+b)$ 。

對於 $B$ -bit machine words，若每個 digit 取 $r$ bits，則 $d=\lceil B/r\rceil$ 、 $b=2^r$ ，所以成本為 $\Theta(\lceil B/r\rceil(n+2^r))$ 。較大的 digit 減少 passes，卻擴大 counter array；較小的 digit 使用更緊湊的 counters，卻要多次掃描 array。

所以「linear」是有條件的： $K=O(n)$ 時 counting sort 才是 $\Theta(n)$ ；若 representation 使 $d$ 為常數且 $b=O(n)$ ，LSD radix sort 才是 $\Theta(n)$ 。負數、變長表示或巨大 key universe 都需要額外處理，不能直接宣稱無條件線性。

定理 / 命題

定理

Quickselect 為何不需要完整排序

假設 Partition 滿足 pivot-final-index 契約。若返回 index $p$ ，局部第 $p+1$ 小就是 pivot；更小的目標 rank 在 left subarray；更大的目標 rank 在 right subarray，並調整為 $k-p-1$ 。因此每次 partition 後至多只需一次 recursive call。

定理

比較排序的 decision-tree 下界

對於由 $n$ 個互異 key 組成的任意 input，任何只透過 key comparison 得知相對次序的 deterministic sorting algorithm，都存在需要 $\Omega(n\log n)$ 次 comparisons 的 worst-case execution。若有界整數可以用作 array index，這個模型假設便不再適用。

定理

LSD radix sort 的正確性

完成 digit $0,1,\ldots,j$ 的 stable passes 後，array 按照由這 $j+1$ 個低位組成的 base- $b$ suffix 排好。處理全部 $d$ 位後，這個 suffix 就是完整 key，所以 array 完全有序。

證明思路

Quickselect 的分支正確性與成本

Partition 後，pivot 位於它在完整 sorted current subarray 中可以佔據的最終位置；左邊所有 key 不大於它，右邊所有 key 不小於它。因此 target index 小於 $p$ 時毋須右邊，大於 $p$ 時毋須左邊，相等時立即 return。兩邊內部毋須已經有序。

每次 partition 在長度 $m$ 的 subproblem 上花 $\Theta(m)$ 。若 pivot 每次都極端，size 依次為 $n,n-1,\ldots,1$ ，所以 $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$ 。若每次恰好縮半， $n+n/2+n/4+\cdots$ 的 geometric sum 只是線性成本的直覺，不能單獨當作 average-case proof。

對 randomized three-way variant，明確假設每次從目前 subarray 中 uniform、independent 地選擇一個 record，並且 comparison 與 swap 是 constant time。把相等 occurrences 任意賦予 sorted order 中連續的 ranks。所選 record 的 rank 落在中間一半的概率至少為 $1/2$ ；一旦發生，它的 strict-less 與 strict-greater blocks 都至多為 $3m/4$ 。目標要麼在 equal block 直接 return，要麼只在其中一個 strict block 繼續。得到一次這種 constant-factor shrink 所需嘗試次數期望至多為 2，每個 size scale 的 expected work 是 $O(m)$ 。對逐層縮小的 scales 求和得到 expected $O(n)$ ；第一次 partition 又給出 $\Omega(n)$ ，所以 expected time 為 $\Theta(n)$ 。 All-equal input 只需一次 linear pass；若 keys 互異而 pivots 每次都極端， worst case 仍為 $\Theta(n^2)$ 。

Decision-tree 下界證明

$n$ 個互異 arbitrary keys 有 $n!$ 種相對次序。Deterministic comparison sort 可以表示成 binary decision tree：internal node 是一次 comparison，leaf 必須識別一種 input permutation，所以正確演算法至少需要 $n!$ 個 leaves。高度 $h$ 的 binary tree 最多有 $2^h$ 個 leaves，因此 $h\ge\log_2(n!)$ 。令 $q=\lfloor n/2\rfloor$ 。 $n!$ 中最大的 $q$ 個 factors 都至少為 $\lceil n/2\rceil$ ，所以

\log_2(n!)\ge \left\lfloor\frac n2\right\rfloor \log_2\!\left(\left\lceil\frac n2\right\rceil\right) =\Omega(n\log n).

所以至少一個 input 要走過這麼長的 path。Counting sort 與 radix sort 使用 digit extraction、arithmetic 和 direct addressing，並限制 key representation，因此不違反這個只針對 comparison model 的結論。

LSD radix invariant

對 pass 數作 induction。Digit $0$ 排完後，array 按最低位有序。假設已經按 digits $0$ 至 $j-1$ 組成的 suffix 有序；下一次 stable pass 按 digit $j$ 排序。Current digit 不同的 records 由本輪直接排好；current digit 相同的 records 保持上一輪相對次序，因此仍按較低位 suffix 排好。於是處理 digit $j$ 後，array 按更長 suffix 有序。直至 digit $d-1$ ，suffix 等於完整 key。

例題詳解

例題

Partial selection 的成本

對 tutorial array $[11,6,43,7,14,28,9,2,4,37,18,34,8]$ 找第 4 小，partial selection 依次把 $2,4,6,7$ 放到前四個位置。 $n=13,k=4$ 時，四次 suffix scan 共作 $12+11+10+9=42$ 次 comparisons，返回 A[3]=7。

完整 selection sort 要作 $78$ 次 comparisons；這裏節省工作是因為 $k$ 小。若找 median， $k=\Theta(n)$ ，partial selection 仍為 quadratic。

例題

Quickselect partition trace

在 $[56,25,37,58,95,19,73,30]$ 中找第 2 小，並採用 tutorial 的 first-element pivot。

以 $56$ partition，得到 $[19,25,37,30,56,95,73,58]$ 。Pivot index 為 $4$ 、rank 為 $5$ ，所以只保留 left subarray $[19,25,37,30]$ 。
以 $19$ partition，pivot 局部 rank 為 $1$ 。目標在右邊，新 rank 是 $2-1=1$ 。
在 $[25,37,30]$ 中，pivot $25$ 的局部 rank 為 $1$ ；相等分支 return $25$ 。

被捨棄部分毋須 sort。這個 trace 亦說明 equality return 與 right-rank adjustment 缺一不可。

例題

Counting sort：從計數到 stable placement

令 $A=[0,5,3,2,3,0,5,1,5,2]$ 且 $K=5$ 。Keys $0$ 至 $5$ 的六個 counters 為

$C=[2,1,2,2,0,3].$

Prefix accumulation 後得到

$C'=[2,3,5,7,7,10],$

其中 $C'[i]$ 是不大於 $i$ 的 key 數。從右到左掃描 $A$ ，對 key $x$ 執行 B[--C'[x]] = record。例如最右的 $2$ 先把 counter $5$ 減為 $4$ ，再放到 zero-based index $4$ 。最終

$B=[0,0,1,2,2,3,3,5,5,5].$

若相同 key 帶有不同 record identity，從右到左處理會讓 input 中較後的 record 佔據較後的 output position，從而保持相對次序。三階段成本分別是 $\Theta(n)$ 、 $\Theta(K+1)$ 、 $\Theta(n)$ ，合計 $\Theta(n+K)$ 。

例題

Radix sort 為何需要 stability

對 $[329,457,657,839,436,720,355]$ 執行 base- $10$ LSD radix sort：

stable ones-digit pass： $[720,355,436,457,657,329,839]$ ；
stable tens-digit pass： $[720,329,436,839,355,457,657]$ ；
stable hundreds-digit pass： $[329,355,436,457,657,720,839]$ 。

以 tens pass 為例，tens digit 同為 $2$ 的 $720$ 與 $329$ 保持上一輪根據 ones digit 建立的次序。Unstable pass 可能把它們逆轉，破壞 induction hypothesis。

常見錯誤

接受 $k=0$ 或 $k>n$ ，或混淆 1-based rank 與 0-based index。
把普通 partition boundary 當成 pivot 最終 index。
省略 quickselect 的 equality return，或進入右邊時沒有減去 $p+1$ 。
說 quickselect 永遠 linear，沒有 uniform randomized-pivot model 就把 balanced shrink 當成 average-case proof，或在允許 duplicates 時漏掉 three-way equal block。
寫 sorting「至少是 $O(n\log n)$ 」。下界要寫 $\Omega$ ，並要說明 arbitrary distinct inputs 與 comparison-only assumptions。
對 inclusive range $0,\ldots,K$ 只分配 $K$ 個 counters，或沒有把全部 $K+1$ 個 counters 初始化為零。
把標準 stable counting sort 說成 in-place，或在遞減 prefix position 時從左到右掃描 input。
對所有 radix-sort organization 作同一個 stability 聲明；本節定理專指 whole-array LSD passes。

總結

Selection 只返回一個 order statistic；sorting 返回全部 rank information。
Partial selection 成本為 $O(kn)$ ，只在 $k$ 小時有吸引力。
Source two-way final-index trace 讓 quickselect 只進入一邊；duplicate-safe uniform randomized three-way variant 會在 equal block 直接 return，expected time 為 $\Theta(n)$ 。All-equal input 是 $\Theta(n)$ ，worst case 是 $\Theta(n^2)$ 。
Arbitrary distinct keys 的 comparison sorting 由 decision-tree proof 得到 worst-case $\Omega(n\log n)$ comparisons。
對 keys $0,\ldots,K$ ，stable counting sort 使用 $K+1$ 個 counters，時間 $\Theta(n+K)$ ，從右到左掃描以保證 stability；標準 output-array 版本不是 in-place。
含 $d$ 個 base- $b$ digits 的 LSD radix sort 使用 stable digit passes，成本 $\Theta(d(n+b))$ ；是否線性取決於 representation parameters。

練習

思考檢查

為甚麼 full sorting 比 selection 做更多工作？

比較題目要求的 output。

解答 · 答案

Selection 只要一個 ranked element；sorting 要知道所有元素的完整次序。