Wednesday, December 28, 2011

Quick Sort

之前一直不曾親自寫過Quick Sort(簡稱qsort),所以這回來練習一下。

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 &gt; 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(&amp;arr[pivInd], &amp;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&lt;=(right-1) ; i++){
  if(arr[i] &lt; pivVal){
   swap(&amp;arr[stoInd++], &amp;arr[i]);
  }
 }

 // swap back the pivot and the last element
 swap(&amp;arr[stoInd], &amp;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;
}

參考資料: