Created
March 23, 2010 03:58
-
-
Save chucknthem/340826 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <malloc.h> | |
#include <assert.h> | |
void printArray(int *array, int low, int high) { | |
while(low <= high) { | |
printf("%d ", array[low++]); | |
} | |
printf("\n"); | |
} | |
void swap(int *a, int *b) { | |
int tmp = *a; | |
*a = *b; | |
*b = tmp; | |
} | |
/* | |
* pick a pivot index between low and high inclusive | |
*/ | |
int getPivot(int *array, int low, int high) { | |
return low; | |
} | |
/* | |
* @return the position of the pivot | |
*/ | |
int partition(int *array, int low, int high, int pivot) { | |
int cur = low; | |
swap(&array[pivot], &array[high]); | |
while (low <= high) { | |
if(array[low] < array[high]) { | |
swap(&array[low], &array[cur]); | |
cur++; | |
} | |
low++; | |
} | |
swap(&array[cur], &array[high]); | |
return cur; | |
} | |
void qsortLH(int *array, int low, int high) { | |
if(low < high) { | |
int pivot = getPivot(array, low, high); | |
pivot = partition(array, low, high, pivot); | |
qsortLH(array, low, pivot - 1); | |
qsortLH(array, pivot + 1, high); | |
} | |
} | |
int main(int argc, char**argv) { | |
int *array = (int *) malloc(sizeof(int)*8); | |
array[0] = 1; | |
array[1] = 4; | |
array[2] = 6; | |
array[3] = 58; | |
array[4] = 4; | |
array[5] = 2; | |
array[6] = 7; | |
array[7] = 23; | |
printArray(array, 0, 7); | |
qsortLH(array, 0, 7); | |
printArray(array, 0, 7); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment