【舌尖上的演算法】Day16 -- Divide and Conquer - Quick Sort

2020 IT邦鐵人賽

Posted by Hank Lee on Wednesday, September 23, 2020

3 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

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


Quick Sort的流程

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

Quick Sort-pivot

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

Quick Sort-Sample

在這個範例中,我們取用陣列的第一個數值作為基準點(Pivot),然後依序從用第二個位置(i)和最後一個位置(j)的值開始進行與Pivot的比較,若兩個值都比Pivot還大,那就會從j開始一步一步往前移動,並與i的值做比較,當j的數值比i小時,ij兩個就會交換,交換過後,再改成從i的位置一步一步往後移動,並與j的值比較,當i的值比j大時,ij再次交換,反覆這個動作,直到ij插肩而過(此時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