11月 11, 2008

【演算】快速排序法 - Quicksort

@
快速排序法(quicksort)是目前被認為效率最高的排序演算法(sorting algorithm)。與合併排序法(mergesort)類似,快速排序法也是利用分治法(divide and conquer,D&C),不斷地將資料分成兩部分以解決問題的例子。


首先,快速排序法會從所有資料中選擇一個支點(pivot)(支點的挑選往往決定了快速排序法的執行效率。為了簡單起見,這裡我們都直接挑選最左邊的資料為支點)。然後,(假設我們需要將資料由小排到大)我們需要把所有小於支點的資料移動到支點之前、並把所有大於支點的資料移動到支點之後。

至於要怎麼移動呢?首先,我們先從資料的最左邊開始,尋找一個比支點還大的數字。並且同樣的,從資料的最右邊開始,尋找一個比支點還小的數字。接著,將兩筆資料交換。並重複同樣的動作,直到資料已分為「比支點小」與「比支點大」兩堆後,再將支點移動到兩者之間即可。

移動完成之後,我們將資料根據支點分割(partition)成兩份,再分別對其進行相同的挑選支點並移動的動作,直到完全排序完成為止。


舉例來說,若我們需要將以下資料由小排到大:

26 13 73 31 38

我們先從資料中挑選一個支點:

26 13 73 31 38

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊:

13 26 73 31 38

將資料根據支點分成兩邊:

(13) 26 (73 31 38)

左邊的資料完成排序。從右邊的資料挑選支點:

13 26 (73 31 38)

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊:

13 26 (38 31 73)

將資料根據支點分成兩邊:

13 26 (38 31) 73

接下來以此類推:

13 26 (38 31) 73

13 26 (31 38) 73

13 26 (31) 38 73

直到排序完成:

13 26 31 38 73


虛擬碼大致如下:

void quicksort(Type data[1..n], Index left, Index right)
{
    if (left >= right) { return; }

    Type pivot = data[left];

    Index i = left + 1;
    Index j = right;
    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        exchange data[i] and data[j]
    }

    exchange data[left] and data[j]

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}


與先前介紹的合併排序法相同的,快速排序法比較的次數不易去計算,所以我們省略這個過程。不過需要知道的是,在最差情況時,快速排序法的執行時間會隨著資料大小為 n 的變化,形成 n2 曲線成長。

雖然看起來執行效率不佳,但是在平均情況下,快速排序法執行時間的成長速率卻只有 n log n!可見在大多數情況下,快速排序法的效率仍然是相當優秀的。


以下是使用 C 語言的實現:

#include <stdio.h>
#include <stdlib.h>

void quicksort(int *data, int left, int right);
void swap(int *a, int *b);

int main(void)
{
    int i, n, data[10];

    printf("請輸入資料筆數 n(<= 10): ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        printf("請輸入第 %d 筆資料: ", i + 1);
        scanf("%d", &data[i]);
    }

    // 執行快速排序法
    quicksort(data, 0, n - 1);

    printf("\n排序後的結果: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", data[i]);
    }

    printf("\n");
    system("pause");
}

void quicksort(int *data, int left, int right)
{
    int pivot, i, j;

    if (left >= right) { return; }

    pivot = data[left];

    i = left + 1;
    j = right;

    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        swap(&data[i], &data[j]);
    }

    swap(&data[left], &data[j]);

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

8 回覆:

匿名 提到...

start from

26 13 73 31 38

everytime pick the left one as piviot

so
it's
13 26(done) 73 31 38

13(done) 26(done) 73 31 38

13(done) 26(done) 31 38 73(done)

13(done) 26(done) 31(done) 38 73(done)

13(done) 26(done) 31(done) 38(done) 73(done)

匿名 提到...

you typed

將資料根據支點分成兩邊:


(13) 26 (38 31 73)


but the origin one is 31 38 73

you typed sth wrong ??

小參 提到...

確實是我打錯了, 不好意思

匿名 提到...

已範例來說,(13) 26 (38 31 73)這時候左邊以排序完成,如果碰到左邊未排序完成時,要將左邊第一個點當作pivot繼續排序到完為止吧?那麼左邊都排序完後如何在選新的pivot呢?

路人甲 提到...

13(done) 26(done) 73 31 38之後
應該是13(done) 26(done) 38 31 73(done) 吧

Chi-En Wu 提到...

感謝,已更正。

甲路人乙 提到...

你在while(1)裡頭有一個判斷i是否大於j 成立的話 break while(1).不成立就交換i j,那你交換完i j 是不是要再加一個break?? 不然會一直在while(1)中出不來

匿名 提到...

10,13,11,15 無法排序 程式有問題

張貼留言