實作快速排序法

練習以遞迴方式實作 "快速排序法 (quick sort)"

問題: 將整數陣列中存放的資料由小到大重新排列

快速排序演算法分析:

舉例來說, 陣列中存放 n=9 筆資料 (9, 5, 12, 19, 2, 6, 4, 15, 8, 3, 7), 整個排序演算法的目標是希望最後陣列裡的資料由小排到大 (2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 19)

快速排序演算法運用 Divide and Conquer 的概念, 希望找到一個中間值, 把陣列中的資料分為兩半, 其中一半比這個中間值小, 另外一半大於等於這個中間值, 如此就可以把問題拆成兩半各自排序, 使得問題的大小逐步減低, 也就非常適合設計遞迴演算法

如上所述我們先針對如何 "切分問題" 來設計: 首先我們指定這個中間值為陣列的第一個元素, 以上例來說就是 9, 然後需要把陣列裡的資料分成 "比 9 小" 的集合 {5, 2, 6, 4, 8, 3, 7} 以及 "大於等於 9" 的集合 {12, 19, 15}, 並且把 9 這個元素放在陣列的第 8 個, 把 "比 9 小" 的集合裡所有元素放在陣列前 7 個位置, 把 "大於等於 9" 的集合裡所有元素放在陣列後 3 個位置

如下圖: 我們運用三個變數 pivot, front, rear 分別指向 "中間值 9", "目前位置在中間值之前", "目前位置在中間值之後" 的元素, 並且交換, 如果 front 內容大於 "中間值" 而且 rear 內容小於 "中間值" 則將兩者指向的資料互換, 直到 front 與 rear 指到相同的位置

遞迴演算法設計:

由上面的演算法描述中可以看到問題在 divide-and-conquer 的精神下, 困難度逐步降低, 這很適合運用遞迴方法來設計程式, 在設計遞迴時一般需要專注於

1. 如何擴大戰果, 由兩個排序完成的子集合擴充到 n 個元素排序完成的狀態,
　 在 "快速排序法" 中這個部份就是上一步驟所描述如何把 "中間值" 移到正確的位置,
　 把比它小的元素放在左手邊的陣列中, 大於或是等於它的元素放在右手邊的陣列中;
2. 確定遞迴結束的條件;
3. 呼叫自己完成兩個子集合裡元素的排序

快速排序法的遞迴演算法:

1. if n is not larger than 2
      2. compare directly and declare the array sorted
   else
      3. move the pivot value to the place it belong in the array, smaller values to the left and larger values to the right 
      4. sort the two subarrays {array[0] .. array[pivot-1]} and {array[pivot+1] .. array[n-1]}

快速排序法運作的過程中如果每次的中間值剛好都位於陣列的中點, 程式的運作效率最好, 大約是 O(n log n), 
如果運氣很差, 每一次的中間值都在陣列的兩端, 這時運算的效率最差, 大約是 O(n2)

遞迴程式實作:

place_midst: (step 3)

int place_midst(int array[],   /* input/output - array in which to split 	*/
                int n)         /* input - number of array elements to consider   	*/
{
    int tmp, front = 1, rear = n-1;
    while (rear >= front)
    {
	    while (front<n && array[front]<array[0]) // < for stable sort
            front++;
        while (rear>=0 && array[rear]>=array[0]) // >= for stable sort
            rear--;
        if ((rear>=1)&&(front<n)&&(rear>front))
        {
            tmp = array[rear];
            array[rear] = array[front];
            array[front] = tmp;
        }
    }
    if (rear>0)
    {
        tmp = array[rear];
        array[rear] = array[0];
        array[0] = tmp;
    }
    return rear;
}

quick_sort: (step 4)

void quick_sort(int array[],  /* input/output - array to sort 	*/
                int n)        /* input - number of array elements to sort	*/
{   
    if (n > 2) 
    {
        int pivot = place_midst(array, n);
        quick_sort(array, pivot);
        quick_sort(&array[pivot+1], n - pivot - 1);
    }
    else if (n == 2)
    {
        int tmp;
        if (array[0]>array[1])
        {
            tmp = array[1];
            array[1] = array[0];
            array[0] = tmp;
        }
    }
}

5