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;
}

參考資料：

• http://en.wikipedia.org/wiki/Quicksort
• http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/