Quick Sort運用到Divide and Conquer的觀念，即是當我們把問題分到很小很小的時候，小問題相對容易解決，而每一個小問題解決之後，大問題也順勢被解決了。其中，把資料分成一半，一半再分成一半...的循環是很常見的。
Qucik Sort的方法是在原本資料中隨意取出一個element當作pivot，將所有小於此資料的elements放到pivot的左邊，大於者放到右邊，接著分別在左右邊的所有elements中另外各取一個pivot，遞迴地重複一樣的事情，直到分割出來的資料大小是零或是一後便不再分割，最後把所有被分割的資料依序組合起來，整個資料便會照順序排列了。
為了不使用額外的記憶體空間，實際撰寫程式處理單一問題（把小於pivot者放右邊、反之左邊，以下code中稱作partition）時，先把pivot放到最右邊，掃過左邊其餘的elements，發現第一個比pivot小的讓他跟左邊第一個element對換位置，發現第二個比pivot小的讓他跟左邊第二個element對換位置，以此類推下去。
#include <stdio.h>
// Function Declarations
void qsort(int *arr, int left, int right);
int partition(int *arr, int left, int right, int pivInd);
void swap(int *a, int *b);
void printArr(int *arr, int len);
/*
* Function : main
*/
int main(void){
int arr[8] = {6,5,2,3,8,1,7,4};
// print out original array
printArr(arr, sizeof(arr)/sizeof(arr[0]));
// qsort here
qsort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
// print out the array after sorting
printArr(arr, sizeof(arr)/sizeof(arr[0]));
return 0;
}
/*
* Function : qsort
* By using divide and conquer, we keep finding a pivot
* and make the elements which are smaller than it in
* front of the pivot.
*/
void qsort(int *arr, int left, int right){
if(right > left){
//divide
int pivInd = (right + left) / 2;
pivInd = partition(arr, left, right, pivInd);
//conquer
qsort(arr, left, pivInd-1);
qsort(arr, pivInd+1, right);
}
}
/*
* Function : partition
* Make the elements which are smaller than arr[pivInd] in
* front of the pivot. And return the index of the original
* arr[pivInd].
*/
int partition(int *arr, int left, int right, int pivInd){
// pivot value, store index
int pivVal = arr[pivInd];
int stoInd = left;
// swap the pivot and the last element
swap(&arr[pivInd], &arr[right]);
// scan through the arr from left to right-1
// make the elements which are smaller than pivVal in the font
int i;
for(i=left ; i<=(right-1) ; i++){
if(arr[i] < pivVal){
swap(&arr[stoInd++], &arr[i]);
}
}
// swap back the pivot and the last element
swap(&arr[stoInd], &arr[right]);
// return the index where the original arr[pivInd] stores
return stoInd;
}
/*
* Function : swap
* Swap to variables by passing two pointers.
*/
void swap(int *a, int *b){
int t;
t = *a;
*a = *b;
*b = t;
}
/*
* Function : printArr
* Print out the array
*/
void printArr(int *arr, int len){
while(len--)
printf("%d ",*arr++);
printf("\n");
}
然而，實際上C語言的stdlib.h中有qsort函式可以直接拿來用：
qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
完整範例如下：
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b){
return ( *(int *)a - *(int *)b);
}
void printArr(int *arr, int len){
while(len--)
printf("%d ",*arr++);
printf("\n");
}
int main(void){
int arr[8] = {6,5,2,3,8,1,7,4};
int len = sizeof(arr)/sizeof(arr[0]);
printArr(arr, len);
// qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
qsort(arr, len, sizeof(arr[0]), compare);
printArr(arr, len);
return 0;
}
參考資料：
