本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

昨天介紹了第一種Divide and Conquer的演算法(Merge Sort)，今天我們要來講第二個屬於這個類別的演算法-Quick Sort。

Quick Sort的流程

相較於其他Sorting的演算法，Quick Sor算是比較特殊的一種，為什麼這麼說呢？因為經由Quick Sort執行過後的結果並非是一個正序或倒序排列的結果，反而僅僅是依照大小分為兩邊而已(如下示意圖）。

因為要依照數值大小分兩邊，就必須要有一個基準點(pivot)，然後將其他數值去跟這個pivot做比較，再分配到兩邊（如圖中的紅色和藍色的區塊）；而至於實際上數值怎麼交換位置，我們看看下面的範例好了：

在這個範例中，我們取用陣列的第一個數值作為基準點(Pivot)，然後依序從用第二個位置(i)和最後一個位置(j)的值開始進行與Pivot的比較，若兩個值都比Pivot還大，那就會從j開始一步一步往前移動，並與i的值做比較，當j的數值比i小時，i和j兩個就會交換，交換過後，再改成從i的位置一步一步往後移動，並與j的值比較，當i的值比j大時，i和j再次交換，反覆這個動作，直到i和j插肩而過（此時j在前，i在後），這兩個指標所在位置的兩個數值會交換兩次，交換兩次後，pivot的數值會再與j的數值交換位置，如此以來，Pivot的左手邊都會是比其小的數值，而右手邊則反之。Pseudo-Code在下方，請自行參閱：

function QPartition(Array[l,...,r]){
    p = Array[l];
    i = l;
    j = r + 1;
    repeat
        do
            i = i + 1
        while Array[i] < p and i < r
        do
            j = j - 1
        while Array[j] > p
        swap(Array[i], Array[j])
    until i >= j
    swap(Array[i], Array[j])
    swap(Array[l], Array[j])
    return j
}

// Input: A subarray Array[l,...,r] of Array[0,...,n-1]
// Output: A subarray Array[l,...,r] sorted in ascending order.
function QuickSort(Array[l,...,r]){
    if l < r {
        // s is the index to split the array
        s = QPartition(Array[l,...,r])
        QuickSort(Array[l,...,s-1])
        QuickSort(Array[s+1,...,r])
    }
}

Quick Sort的時間複雜度

1. Best Case:

發生的情況是這個挑選的Pivot可以剛剛好將一個陣列切成左右對等長度的兩個子陣列，如此一來，其時間複雜度為Ｏ(n·㏒2 n)。

2. Worst Case:

如果Pivot選擇的不好，那等於會讓某一個切出來的子陣列是空的，這種狀況通常出現在陣列已經排序過了（正序或倒序），這樣的話，期時間複雜度為Ｏ(n^2)。

3. Average Case:

統計的結果是Average Case的比較次數大概會是Merge Sort的1.39倍，因此其時間複雜度為Ｏ(1.39n·㏒2 n)。

小結

1. Quick Sort是到目前為止介紹的Sorting演算法中唯一一個結果沒真正排序的演算法。
2. Quick Sort的時間複雜度對於Best Case, Worst Case和Average Case來說都不相同。

預告

明天我們將會進入另一個主題-Transform and Conquer。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin