3.3.1 - Quick Sort

1. 演算法

採用Divide and Conquer策略。選定一個pivot key使得:

1. A[1]~A[q-1] ≤ p.k

2. A[q+1]~A[n] ≥ p.k

此時資料被分成左右兩個sublist，再各自排列，當左右sublist排完，整個資料也就排序完成。

排序步驟範例:

$A[8]=\{5,9,8,2,3,6,4,7\} \Rightarrow p.k=5$

$i$ 找到大於p.k的位置， $j$找到小於p.k的位置 $\Rightarrow A[1]=9,\ A[6]=4$

$swap \Rightarrow \{5,\underline{4},8,2,3,6,\underline{9},7\}$

$i$ 找到大於p.k的位置， $j$找到小於p.k的位置 $\Rightarrow A[2]=8,\ A[4]=3$

$swap \Rightarrow \{5,4,\underline{3},2,\underline{8},6,9,7\}$

當 $i≥j$時，p.k和 $A[j]$交換位置，此時 $j=3$

$\Rightarrow \{[2,4,3],5,[8,6,9,7]\}$

採用同樣方法sort({2,3,4})、sort({8,6,9,7})

void Sort(char *arr, int l, int u){
    if (l >= u) return; //判斷sorting結束
    int pk = arr[l];    //選pk
    int i = l;
    int j = u ;
    int temp;
    while (i<j){        //直到i>j
        while (arr[i]<pk) i++;
        while (arr[j]>pk) j--;
        if (i<j){     //swap
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[l];    //j與pk交換位置
    arr[l] = arr[j];
    arr[l] = temp;
    Sort(arr, l, j-1);  //左邊sublist
    Sort(arr, j+1, u);  //右邊sublist
}

2. 性質

• Time Complexity:

  • Best Case: $O(nlogn)$

  $\Rightarrow$ p.k的位置恰將資料分割成兩等份

  $T(n)=C\times n+T(\frac{n}{2})+T(\frac{n}{2})$ C*n為分割所花時間

  $T(n)=2T(\frac{n}{2})+C\times n$

  $T(\frac{n}{2})=2T(\frac{n}{4})+C\times\frac{n}{2}$

  $T(n)=2[2T(\frac{n}{4})+C\times\frac{n}{2}]+C\times n=4T(\frac{n}{4})+2(C\times n)$

  $T(n)=nT(1)+\log_2n(C\times n)$

  • Worst Case: $O(n^2)$

  $\Rightarrow$ p.k恰好是最大值或是最小值，使得分割無效果

  $T(n)=C\times n+T(n-1)$ C*n為分割所花時間

  $T(n)=C(n+(n-1))+T(n-2)$

  $T(n)=C(n+...+2)+T(1)=\frac{C(n+2)(n-1)}{2}$

• Space Complexity: $O(logn)$~ $O(n)$

  $\Rightarrow$ 額外空間需求來自於recursion所需的stack，stack size取決於recursion call的次數。

  • Best Case: $O(logn)$

  $\Rightarrow$ 每次p.k的位置恰將資料分割成兩等份，經過k次呼叫後只剩一筆Data， $\frac{n}{2^k}=1,\ k=log_2n$

  • Worst Case: $O(n)$

  $\Rightarrow$ p.k恰好是最大值或是最小值，使得分割無效果，資料大小為n, n-1, n-2,...，共需n次呼叫

Quick sorting is a unstable sorting method.

$\{3_{p.k},\ 5,\ 5^*,\ 1,\ 2 \} \Rightarrow [1,\ 2],\ 3,\ [5^*,\ 5]$