3.3.1 - Quick Sort

1. 演算法

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

A[1]~A[q-1] ≤ p.k
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:

Quick sorting is a unstable sorting method.

Previous3.3 - Sophisticated Sorting Next3.3.2 - Merge Sort

Last updated 6 years ago

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 }