快速排序 (Quick Sort)

之前介紹過的插入排序、選擇排序、泡泡排序等方法雖然簡單,在演算法的執行效率上卻犧牲了很多,時間複雜度高達 O(n2 )。

現在要介紹的快速排序 (Quick Sort) 是平均狀況下,排序時間最快的方法。

Quick Sort 採用 Divide-and-Conquer 策略──也就是將一個問題切割成幾個獨立的子問題,最後合併所有子問題上的最佳解,作為整個問題的最佳解。

歡迎參考 edX 上開授的 CS 50 課程示範影片:

https://www.youtube.com/watch?v=aQiWF4E8flQ

在數列中隨便找一個數字作為基準 (pivot),然後把該數列中所有比基準數小的數字都放在左邊、比基準數大的數字都放在右邊。

即代表此陣列已經被切割成左、右兩個子陣列。再讓左右兩個子陣列各自做排序,當左、右子陣列排完時,整個排序也就結束了。

關鍵問題是,如何做 Partition (分割)?這個問題也就是如何決定基準的正確位置。

虛擬碼 (這裡的虛擬碼是cormen演算法書上提供的作法)
Partition(A, left, right)
  pivot = A[right]
  i = left-1
  for j = left to (right-1) do
    if (pivot>=A[j])
      i = i+1
      swap(A[i], A[j])
    end if
  end for
  swap(A[right], A[i+1])
  return (i+1) //回傳pivot的正確位置


QuickSort(A, left, right) //排序A[left]~A[right]
  if(left<right) then
    i = Partition(A, left, right)
    QuickSort(A, left, i-1)
    QuickSort(A, i+1, right)
  end if

用最後一格當作 pivot。

程式碼(這裡是hORWITZ提供的作法)
#include <stdio.h>

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

int quick_sort(int A[], int left, int right) //排序A[left]~A[riht]
{
  int pivot;
  int i, j;
  if(left < right){
    pivot = A[left];
    i = left;
    j = right+1;
    while(i<j){
      while(pivot>A[i])
        i++;
      while(pivot<A[j])
        j--;
      if(i<j) //直到i ,j兩軍交會
        swap(&A[i], &A[j]);
    }
    while(i<j) //要不要加這個while??
      swap(&A[left], &A[j]);
    quick_sort(A, left, j-1);
    quick_sort(A, j+1, right);
  }
};

int main(){
  int count, i;
  scanf("%d", &count);
  int list[count];
  printf("Numbers to be sorted: ");
  for(i = 0; i<count; i++){
    scanf("%d", &list[i]);
    printf("%d ", list[i]);
  }
  printf("\n");
  quick_sort(list, 0, count-1);
  printf("Numbers Sorted: ");
  for(i = 0; i<count; i++){
    printf("%d ", list[i]);
  }
  printf("\n);
  return 0;
}

 

時間複雜度

1. Best Case: O(n log n)

Pivot 的正確位置恰好將資料陣列切割成兩等分。

  • c*n: Partition 所花時間為 O(n) 或 c*n
  • T(n/2) 分別為左、右串列遞迴做 Quick Sort 的時間

  ,其中 c 為正常數, T(1) = 0

故時間複雜度為 O(n log n)

 

2. Worst Case: O(n2)

Pivot 恰好是該資料陣列的最小值或最大值,使得切割無法產生一分為二的效果。

T(n) = c*n + T(n-1) + T(0), c*n 為切割時間

T(n) = T(n-1) + c*((n-1)+n) = … = T(1) + c*(2+ … +n)

故時間複雜度為 O(n2)

 

避免 Quick Sort 的 Worst Case 發生

有鑑於時間複雜度高達 n2,要怎麼樣才能避免取到最小或最大值的 Worst Case 呢?

以下提供三種可能解法:

1. Middle-of-Three 方法

(1) 令 middle = (left + right) /2

(2) 比較 A[left]、A[middle] 與 A[right] 這三筆資料,排出中間值。

c. 將此中間值再與 A[left] 做交換

(3) 讓現在新的 A[left] 作為 pivot

如果 pivot 的位置恰好在 n 筆資料中的 n/10 與 9n/10 之間:

      c*n ----------c*n
    /     \
c*n/10  c*9n/10-----c*n
  / \      / \
... ...  ... ... ---c*n
 
T(n) = c*n + T(n/10) + T(9n/10)

還是可以收斂到 O( n log n)。

 

2. Randomized Quick Sort

用亂數選取的方式,隨機挑一個值作為 pivot。

當然,這還是可能會發生 Worst Case 高達 O(n2) 的問題,只是機率比較低。Average Case 與 Best Case 同樣是 O(n log n)。

所以我們也可以把以上兩種改進合併──先用亂數任選三個,再用其中的中間值作為 pivot。

 

3. 使用 Median-of-Medians 作為基準

(1) 將 n 個資料分成 n/5 個堆,每堆有 5 個資料 (可能會有 1 個堆的資料不到 5 個) ,共花 O(n) 時間。

(2) 每堆各由小到大做排序。排序一堆得花 O(52) 時間,可以想成 O(1) 常數。所以當有 n/5 堆排序時,共花 O(n) 時間。

(3) 將排序完、將每堆的第 3 個資料 (也就是中位數) 作為該堆的中間鍵。在這 n/5 堆中,遞迴套用此演算法,求得求出中位數們的中位數 k。 k 即為 median-of-medians ,此步驟花費時間 T(n/5)

(4) 以 k 作為 pivot 重新將堆做排序,花 O(n) 時間。

到這個步驟為止,所花費的時間:T(n) = O(n) + O(n) +T(n/5) + O(n) + ???。問號的地方就是來看看第 (5) 個步驟:

(5) 至少有一半的堆(扣掉 pivot 自己、及不到 5 個資料的堆)、每堆必有 3 個資料大於等於 pivot。

也就是說,至少會有  個資料,化簡為  個資料大於等於 pivot。

(7n/10)+6  個資料---------pivot ---- (3n/10)-6 個資料

此 (5) 步驟的 Worst Case 為 

全部步驟的 Worst Case 即為 

      c*n -----------c*n
    /     \
 c*n/5  c*7/10n------c*9/10*n
  / \      / \
... ...  ... ... ----c*(9/10)^2*n

可知最後的時間複雜度成功降到了 O(n)!

 

空間複雜度

位於 O(log n) ~ O(n) 之間。額外空間需求來自於遞迴所需的 Stack 空間,而 Stack Size 取決於 Recursive Call 的次數。

1. Best Case:

經過 k 次的遞迴呼叫後,達到 1 筆資料後即可停止。

n/2 筆資料 --------- pivot --------- n/2 筆資料 
n/4 筆資料 --- pivot --- n/2 筆資料
n/8 筆資料 -- pivot -- n/8 筆資料
...
1 筆

$latex \frac{n}{2^{k}} $ = 1 筆,故 $latex k = \log_{2}n $ 。

2. Worst Case:

pivot 為最大或最小值

pivot ------------ (n-1) 筆資料
     pivot ------- (n-2) 筆資料
          pivot -- (n-3) 筆資料
                ...
               (n-k) = 1 筆資料

k = n-1,故空間高達 O(n)。

 

穩定性: UNSTABLE

input data: 3 , 5 , 5* , 1 , 2
pivot: 3
--------------------------------
Pass 1: 3 , 2 , 5* , 1 , 2
Pass 2: 3 , 2 , 1 , 5*, 5
Pass 3: 1 , 2 , 3 , 5* , 5

可以發現到最後 5 和 5* 的位置交換了。