iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 9

Day-9 Divide-and-Conquer-4 : Quicksort, 隨機化Quicksort

Quicksort- Tony Hoare - 1962

和merge-sort一樣,他使用了Divide and conquer的想法,下面是對於一個陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...r%5D進行快速排序的三步分治過程

  • Divide : 在陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...r%5D中找到一個元素https://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%5D,把這個元素作為基準點,將陣列拆分成兩個子陣列,https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...q%20-%201%5D中每一個元素皆小於等於https://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%20%2B%201...r%5D中每一個元素皆大於等於https://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%5D
  • Conquer : 通過遞迴呼叫Quicksort,對https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...q%20-%201%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%20%2B%201...r%5D進行排序。
  • Combine : 因為子陣列都是在原陣列中進行排序,就如同插入排序法一樣,所以不需要合併。
QUICKSORT(A, low ,high)
    if low < high
        q = PARTITION(A, low, high)
        QUICKSORT(A, low, q-1)
        QUICKSORT(A, q+1, high)

為了排序A陣列中所有元素,一開始呼叫QUICKSORT(A, 1, A.lenght)

接著開始拆分陣列,這也是Quicksort的關鍵步驟

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            exchange A[i] with A[j]
    exchangeA[i + 1] with A[high]
    return i + 1

選取一個pivot,也就是基準點,以他為基準進行陣列的拆分,程式進行的過程中會將陣列拆分成四個部分,每一個部分都會滿足一定的性質,如小於等於pivot等等...,這樣的性質可以做為循環不變量使用。

整個Quicksort的概念,以A = {6 10 13 5 8 3 2 11}作為舉例

6 10 13 5 8 3 2 11, 選取6作為pivot
^  ^
i  j        ,j開始往後走,直到找到元素小於pivot, 找到時, 進行交換
------------------------------------------------------
6 10 13 5 8 3 2 11
  ^     ^
  i     j  ,i = i + 1
------------------------------------------------------
6 5 13 10 8 3 2 11
  ^     ^
  i     j  ,交換
------------------------------------------------------
6 5 3 10 8 13 2 11
    ^         ^
    i         j
------------------------------------------------------
6 5 3 2 8 13 10 11
      ^           ^
      i           j->
------------------------------------------------------
6 5 3 2 8 13 10 11
^     ^
pivot i     ,最後, pivot和i指到的元素進行交換,也就是將pivot移到中間
------------------------------------------------------
2 5 3 6 8 13 10 11
      ^
    pivot
我們會發現pivot左邊都比他小,右邊都比他大

整個程式大約會將陣列劃分成4個部分,如下圖

會劃分成比pivot小的,比pivot大的,pivot本身,若r不等於陣列最後的index,則會有一個部分是和pivot無關的,這個例子中只有三個部分。

C++進行實作

#include <iostream>

using namespace std;
void quick_sort(int *, int, int);
int partition(int *, int, int);
int main(void)
{
    int A[10] = {2, 7, 3, 6, 1, 9, 0, 4, 7, 3};
    quick_sort(A, 0, 9);
    for (auto i : A)
    {
        cout << i << ' ';
    }
}

void quick_sort(int *a, int low, int high)
{
    if (low < high)
    {
        int q = partition(a, low, high);
        quick_sort(a, low, q - 1);
        quick_sort(a, q + 1, high);
    }
}

int partition(int *a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++)
    {
        if (a[j] <= pivot)
        {
            i = i + 1;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

Quicksort效率

Quicksort的執行時間取決於在劃分陣列時是否平衡,而平衡與否取決於劃分的元素。如果劃分時是平衡的,那Quicksort看起來會像是merge-sort一樣,且有一樣的效率。如果劃分的不平衡,則會十分接近插入排序。

最壞情況

如果無法正常的劃分陣列,則Quicksort的效率會十分的低落,如果我們選取的pivot都比其他的數來的大或是小,便無法把陣列平衡的劃分了,而這樣的情況會發生在整個陣列已經排序完畢,或是整個陣列是逆序排列的。也就是當兩個子陣列分別一個出現n - 1個元素,另一個陣列出現0個元素時。
劃分陣列的操作大概需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n)。由於對一個大小為0的陣列進行遞迴呼叫會直接回傳,因此https://chart.googleapis.com/chart?cht=tx&chl=T(0)%20%3D%20%5CTheta(1),因此整個時間複雜度可以表示成下面
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(n%20-%201)%20%2B%20T(0)%20%2B%20%5CTheta(n)%20%3D%20T(n%20-%201)%20%2B%20%5CTheta(n)

https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(n%20-%201)%20%2B%20%5CTheta(n),使用主方法後,得到結果為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2),而插入排序法最壞的情況也是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2),因此,在最壞的情況下,Quicksort的執行效率不比插入排序法來的好。但是對於已經排序好的陣列來說,Quicksort複雜度仍然是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2),此時插入排序法的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n),效率比Quicksort來的好。

總共有n個https://chart.googleapis.com/chart?cht=tx&chl=T(0),每一個https://chart.googleapis.com/chart?cht=tx&chl=T(0)執行時間為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1),因此n個https://chart.googleapis.com/chart?cht=tx&chl=T(0)時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n),整個https://chart.googleapis.com/chart?cht=tx&chl=T(n)
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n)%20%2B%20%5CTheta(n%5E2)%20%3D%20%5CTheta(n%5E2)

最好情況

Quicksort的平均情況接近於其最好情況,而非其最差情況。假設我們在劃分陣列的時候兩邊元素的大小為9:1的形式,我們試著將在個情況下,Quicksort的遞迴式寫出
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(9n%2F10)%20%2B%20T(n%2F10)%20%2B%20cn

我們將遞迴樹畫出,會發現左子樹和右子樹的高度不同,每一層我們將其加總,第一層n需要https://chart.googleapis.com/chart?cht=tx&chl=cn,第二層https://chart.googleapis.com/chart?cht=tx&chl=1%2F10n%20%2B%209%2F10n%20%3D%20n,同樣需要https://chart.googleapis.com/chart?cht=tx&chl=cn,直到深度達到https://chart.googleapis.com/chart?cht=tx&chl=%5Clog_%7B10%7Dn以後,每一層所需要的時間就會小於等於https://chart.googleapis.com/chart?cht=tx&chl=cn,因為右子樹已經停止展開了,因此該層的加總不會到https://chart.googleapis.com/chart?cht=tx&chl=n

我們將每一層所需要的時間進行加總,得到https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20cn%5Clog_%7B%5Cfrac%209%20%7B10%7D%7Dn,加上所有葉子所需要的時間https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n),得到https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20cn%5Clog_%7B%5Cfrac%209%20%7B10%7D%7Dn%20%2B%20%5CTheta(n),這個不等式的上界為https://chart.googleapis.com/chart?cht=tx&chl=O(nlgn),下界為https://chart.googleapis.com/chart?cht=tx&chl=cn%5Clog_%7B10%7Dn%20%2B%20%5CTheta(n),因此可以表示成https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(nlgn),也可以表示成https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(nlgn)。(如果要求嚴謹必須使用代換法進行證明)

我們在來看到如果我們進行Quicksort,剛好遇到恰好將陣列劃分成兩個區塊的情況,可以表示成https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(n%2F2)%20%2B%20T(n%2F2)%20%2B%20%5CTheta(n),使用主定理得到結果為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(nlgn)

到這裡證明完一件事情,即便陣列拆分的極度不平衡,他們的效率是一樣好的,都是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(nlgn)

平均情況

對於Quicksort來說,他的行為取決維陣列中每一個元素的相對位置,而不是元素本身,因此,我們需要對輸入各種情況的頻率做出假設。

假設我們一開始是幸運的,剛好將陣列1:1劃分,接著出現不幸運的情況,將陣列9:1劃分,接著又出現幸運的情況,我們試著分析這樣的情況。假設幸運的情況為https://chart.googleapis.com/chart?cht=tx&chl=L(n),不幸運為https://chart.googleapis.com/chart?cht=tx&chl=U(n)

我們可以列出下面的式子,每一次幸運之後會接著不幸運,不幸運後會接著幸運
https://chart.googleapis.com/chart?cht=tx&chl=L(n)%20%3D%20U(n%2F2)%20%2B%20U(n%2F2)%20%2B%20%5CTheta(n)
https://chart.googleapis.com/chart?cht=tx&chl=U(n)%20%3D%20L(n-1)%20%2B%20L(0)%20%2B%20%5CTheta(n)

使用代換法求解:
https://chart.googleapis.com/chart?cht=tx&chl=L(n),將https://chart.googleapis.com/chart?cht=tx&chl=U(n%2F2)代換掉,先將https://chart.googleapis.com/chart?cht=tx&chl=U(n%2F2)帶入https://chart.googleapis.com/chart?cht=tx&chl=U(n),得到
https://chart.googleapis.com/chart?cht=tx&chl=U(n%2F2)%20%3D%202(L(n%2F2-1)%20%2B%20%5CTheta(n%2F2)),再將其代回https://chart.googleapis.com/chart?cht=tx&chl=L(n),得到
https://chart.googleapis.com/chart?cht=tx&chl=L(n)%20%3D%202(L(n%2F2-1)%20%2B%20%5CTheta(n%2F2))%20%2B%20%5CTheta(n)
https://chart.googleapis.com/chart?cht=tx&chl=%3D%202L(n%2F2-1)%20%2B%20%5CTheta(n) (使用主定理)
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5CTheta(nlgn)

這個情況下,總體來說,我們是幸運的

這張圖表示先出現不幸運的劃分,再出現幸運的劃分,待解決的為https://chart.googleapis.com/chart?cht=tx&chl=(n-1)%2F2%20-%201https://chart.googleapis.com/chart?cht=tx&chl=(n%20-%201)%2F2,也就是灰色矩形的部分

這張圖表示一開始就出現幸運的劃分,待解決的問題同樣是兩個灰色矩形的部分

這裡有一個問題,我們的幸運只考慮陣列劃分的方式,而沒有考慮陣列中元素排序的方式,如果陣列中的元素是已經排序完成的或逆序的,時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2),為了確保我們是幸運的,這裡有兩個做法,第一個為隨機排序陣列中的元素,另一種是隨機選取基準點。

隨機化Quicksort

在討論隨機化Quicksort的平均情況之前,會先假設輸入的數據的所有種組合的機率都是相等的(實際上不會如此),這麼做的好處,就是我們不用考慮輸入陣列元素的順序,不論輸入什麼元素,屆時都將是隨機排序的,而因為Quicksort不會受到元素大小影響,因此元素的數值我們也不用在意了。不同於原本的Quicksort,在已經排序的情況下效率低落。也因此我們不需要對輸入的陣列中元素的分佈有任何假設,像是確定沒有完成排序等等。沒有任何一種輸入是確定會發生最差的執行效率,會產生出最差執行效率的情況取決於隨機數的產生。

現在最差的情況不由輸入決定,而是取決於隨機數產生器,數學上可以去計算出出現最差情況的邊界,得到出現的可能性,為了方便分析,使用隨機選取基準點(pivot)的方式進行隨機化,不同於普通Quicksort每次選取https://chart.googleapis.com/chart?cht=tx&chl=A%5Bhigh%5D作為基準點,我們使用的隨機抽樣為在https://chart.googleapis.com/chart?cht=tx&chl=A%5Blow...high%5D中隨機選取一個元素作為基準點。

達到這一件事情,實踐的方式是將https://chart.googleapis.com/chart?cht=tx&chl=A%5Bhigh%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5Blow..high%5D中隨機選取的元素進行交換。這模做可以確保基準點pivot = https://chart.googleapis.com/chart?cht=tx&chl=A%5Bhigh%5D是機率均等的從陣列https://chart.googleapis.com/chart?cht=tx&chl=high%20-%20low%20%2B%201個元素中隨機選取的(這樣隨機選擇也有可能選取到自己)。

RANDOMIZED-PARTITION(A, low ,high)
    i = RANDOM(p, r)
    exchange A[high] with A[i]
    return PARTITION(A, low, high)
RANDOMIZED-QUICKSORT(A, low, high)
if low < high
    q = RANDOMIZED-PARTITION(A, low, high)
    RANDOMIZED-QUICKSORT(A, low, high - 1)
    RANDOMIZED-QUICKSORT(A, q+1, high)

參考資料:Introduction to algorithms 3rd


上一篇
Day-8 Divide-and-Conquer-3 : 二分搜尋法, 費波那契數列, Strassen’s演算法
下一篇
Day-10 heap與heap sort
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言