ROSALIND｜Quick Sort (QS)

發表於 更新於

使用 quick sort 排序長度為 n 的整數數列

Given: A positive integer $n$ $\leq 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $A[1..n]$.

(https://rosalind.info/problems/qs/)

Quick sort 是基於劃分 (partition) 的排序方法。考慮一個長度為 2 的數列，若隨機挑選一個數字作為基準值，將數列劃分為小於或大於基準值的兩部分。由於各部分僅含一個數字，所以劃分的同時也確定了順序。

不過，如果數列長度大於 2 就只能保證劃分區域間的關係，無法確認個別區域內的數字順序。舉例來說，若以數字 3 為基準 [1, 2, 3, 4, 5] 和 [2, 1, 3, 5, 4] 都滿足劃分的定義，但無法保證基準兩側的數字順序。我們得進一步劃分兩側的子數列，直到各部分的劃分反映其排序為止，這便是 Quick sort 的核心策略。

為此，我們需要一個的劃分數列的輔助函數。由於要在原數列進行排序，而且每次只劃分基準值兩側順序未定的區域，所以要在程式碼裡添加參數（L：左側，R：右側）來界定劃分範圍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def partition(arr: list[int], pivot_index: int, L: int, R: int) -> tuple[int, int]:
    pivot = arr[pivot_index]
    l, i, r = L, L, R
    while i <= r:
        if arr[i] < pivot:
            arr[i], arr[l] = arr[l], arr[i]
            l = l + 1
            i = i + 1
        elif arr[i] > pivot:
            arr[i], arr[r] = arr[r], arr[i]
            r = r - 1
        else:
            i = i + 1
    return l, r

Quick sort 的本體則是透過遞迴關係執行劃分的函數，它持續劃分基準點兩側順序未定的區域，直到劃分出的區域內只剩一個數字，即劃分方式能完整反映數列順序為止。

1
2
3
4
5
6
7
8
9
10
11
import random
def qs(arr: list[int]) -> list[int]:
    def quick_sort(arr, L, R):
        if L >= R:
            return arr
        pivot_index = random.randint(L, R)
        l, r = partition(arr, pivot_index, L, R)
        quick_sort(arr, L, l - 1)
        quick_sort(arr, r + 1, R)
    quick_sort(arr, 0, len(arr) - 1)
    return arr

Quick sort 的執行效率取決於基準值的選取。假設數列的長度為 n，並以其中最大或最小值為基準，那麼每次只會劃出一個數字，例如 [5, 4, 3, 2, 1] 會分為 [5] 和 [4, 3, 2, 1]。這樣的劃分方式需要依序處理長度為 n-1、n-2、…、1 的子數列。由於每次劃分的時間複雜度為 $O(n)$，而剩餘數列的長度為 n-1、n-2、…、1 的等差級數，所以最差情境的時間複雜度為 $O(n^2)。

反之，如果每次選取的基準點恰好將數列分為兩半，那麼遞迴層數變為 $logn$，時間複雜度也降為 $O(nlogn)$。因此，實作時為了避免最差情境，會隨機選取數字作為劃分的基準點。