[每日C] QuickSort 演算法速覽

目標：

• 簡單解釋 QuickSort
• 用正整數建立一組不重複的陣列
• 使用 QuickSort 排序

QuickSort 的概念：

我不想用說的來表示 QuickSort 到底好在哪裡，所以我們先來看個影片：

▲ 縱使在最差的情況下，QuickSort 仍與 BubbleSort 一樣快！

簡單來說，QuickSort 的做法就是(隨機)挑選一個點(球)作為中間點，並將較大(暗)的放在前面，並將較小(亮)的放在後面，此時，一開始挑選的中間點就被放在排序好的位置了(小機器人按下燈號)。

為甚麼做完一步驟之後，中間點就一定會排好？

請看底下的範例，

5	9	4	3	8	1	7	6	2	10
			↑

假設選擇 3 作為中間值，不管排序過程為何，結果一定會像這樣：

大	大	3	小	小	小	小	小	小	小
		↑

所以一定會與排序後的結果相同！

1

2

3

4

5

6

7

8

9

10

接下來，我們只需要重複上面的動作，在前半部(隨機)找挑選一個點作為中間點，並將較大的放在前面，較小的放在後面，於是我們又有一個新的中間點就被放在排序好的位置了！

只要多做幾次，就會發生前半部只有一個元素的狀況，到此，我們完成了”前面”的部分。

接下來，我們也對後半部進行一樣的動作，(隨機)找挑選一個點作為中間點，並將較大的放在前面，較小的放在後面，新的中間點就會被放在排序好的位置；多做幾次，我們就完成了！

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
╰	─	─	─	↑	─	─	─	─	╯
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
╰	↑	─	╯	▓	╰	─	↑	─	╯
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
▓	▓	╰	╯	▓	╰	╯	▓	╰	╯
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
▓	▓	▓	▓	▓	▓	▓	▓	▓	▓

▲ 大概像這樣！（▓代表已排序）

 

QuickSort 的 C 語言實作

建立一不重複的正整數陣列

為了示範排序效果，我們要先建立一個不重複的正整數陣列，所以必須使用到亂數，因此先引入兩個函式庫（Library）檔案

#include <stdlib.h> //rand()
#include <time.h> //time()

為了之後修改方便，我們用 SIZE 來取代數字 10，代表陣列大小，並將它設定在巨集中，讓編譯器在編譯的時候替換回數字，既省記憶體又好維護

#define SIZE 10

我們先假設存在一個函式（function），可以自動用不重複的亂數填滿一個一維陣列

（甚麼？為甚麼一定不能重複？因為這樣才看的出來每一個步驟阿）

void genRandArray(int* array, int size);

設計成必須要指定元素個數是因為要方便之後複製到其他程式使用。

所以主程式目前有這些東西：

int arrayToSort[SIZE] = {0};
genRandArray(arrayToSort, SIZE);

接下來就是實作這個函式（function）了，

首先，在進入函式的一開始，我們就直接以系統時間（time(NULL)）作為亂數種子

srand(time(NULL));

因為要有 size 個亂數，所以用 for 迴圈從 [0] 跑到 [size-1]，依序填入亂數（餘除 20 後加一是為了限制亂數範圍在 1~20）

for (int i=0; i<size; i++)
{
    array[i] = rand()%20+1;\
}

想當然爾，這樣子難免會發生重複的狀況，所以我們要在現實中會在每一次加入元素之前先比較是不是有重複，若有重複就換一個，直到沒有重複為止，做完一輪，一個元素不重複的陣列就跑出來了！

但是在這裡，小獅想要節省一下記憶體空間，反正我要的就是一個放變數的空間，所以乾脆先把產生的亂數暫時放在 array[i] 然後拿它來比較，如果不幸重複在換掉。

看到這裡，你會想用哪一種迴圈？（提示：一開始不管怎樣先執行，之後再判斷條件，而且不知道要執行幾次）

小獅選擇的是 do-while 迴圈，所以會變成這樣

for (int i=0; i<size; i++)
{
    do
    {
        array[i] = rand()%20+1;
    }
    while (/*如果重複了*/);
}

至於”如果重複了”要如何判斷，小獅選擇的方法是直接跟先前產生的亂數（[0] ~ [自己-1]）逐一比較

for (int i=0; i<size; i++)
{
    do
    {
        isDup = false;
        array[i] = rand()%20+1;

        for (int j=0; j<i; j++)
        {
            if (array[j] == array[i])
            {
                isDup = true;
            }
        }
    }
    while (isDup);
}

咦？isDup（is duplicate）要是放在迴圈裡面就會一直宣告呢！感覺好像很耗資源，那就放外面好了，於是整個函式（function）變成這樣：

void genRandArray(int* array, int size)
{
    srand(time(NULL));
    bool isDup = false;

    for (int i=0; i<size; i++)
    {
        do
        {
            isDup = false;
            array[i] = rand()%20+1;

            for (int j=0; j<i; j++)
            {
                if (array[j] == array[i])
                {
                    isDup = true;
                }
            }
        }
        while (isDup);
    }
}

等不及要測試了嗎？加上這個吧！可以讓你輕鬆印出陣列喔！（而且之後會一直用）

void printArray(int* array, int size)
{
    printf("[");
    for(int i=0; i<size; i++)
    {
        printf(" %d", array[i]);
    }
    printf(" ]\n");
}

於是主程式變成這樣：

int main()
{
    int arrayToSort[SIZE] = {0};
    genRandArray(arrayToSort, SIZE);

    printf("Before Sort:\n");
    printArray(arrayToSort, SIZE);
}

印出精美的成果：

Before Sort:
[ 11 20 9 2 16 13 14 17 15 3 ]