## Wednesday, December 28, 2011

### Quick Sort

Quick Sort運用到Divide and Conquer的觀念，即是當我們把問題分到很小很小的時候，小問題相對容易解決，而每一個小問題解決之後，大問題也順勢被解決了。其中，把資料分成一半，一半再分成一半...的循環是很常見的。

Qucik Sort的方法是在原本資料中隨意取出一個element當作pivot，將所有小於此資料的elements放到pivot的左邊，大於者放到右邊，接著分別在左右邊的所有elements中另外各取一個pivot，遞迴地重複一樣的事情，直到分割出來的資料大小是零或是一後便不再分割，最後把所有被分割的資料依序組合起來，整個資料便會照順序排列了。

```#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");
}
```

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