From cb10a5da404bfa914c071c56eab561d905b514db Mon Sep 17 00:00:00 2001 From: Kyle K Date: Thu, 25 Nov 2010 02:18:00 -0600 Subject: implement quicksort --- sorts.c | 48 +++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 45 insertions(+), 3 deletions(-) diff --git a/sorts.c b/sorts.c index 0207fd0..06f5d8c 100644 --- a/sorts.c +++ b/sorts.c @@ -11,8 +11,8 @@ #include #include #include -#define ARR_SIZE 50 -#define ARR_RANGE 13 +#define ARR_SIZE 100 +#define ARR_RANGE 99 #define ELEM_LINE 10 #define FNAME "sort.txt" #undef PRINT_FILE @@ -30,6 +30,47 @@ void mergesort(int *, int, int); void merge(int *, int, int, int); void shell_sort(int *, int); int binary_search(int *, int, int, int); +void quicksort(int, int, int *); + +/* came from CS202 project */ +void quicksort(int low, int high, int *arr) +{ + int lo = low; + int hi = high; + int mid; + + if (high > low) + { + /* set midpoint */ + mid = arr[(low + high)/2]; + + /* loop until base addr reaches end of the arr */ + while (lo <= hi) + { + /* seek until we find strings that need to be swapped */ + while ((lo < high) && (arr[lo] < mid)) + ++lo; + while ((hi > low) && (arr[hi] > mid)) + --hi; + /* swap */ + if (lo <= hi) + { + int tmp = arr[hi]; + arr[hi] = arr[lo]; + arr[lo] = tmp; + + ++lo; + --hi; + } + } + /* sort the left partition */ + if (low < hi) + quicksort(low, hi, arr); + /* sort the right partition */ + if (lo < high) + quicksort(lo, high, arr); + } +} int binary_search(int *a, int low, int high, int target) { @@ -225,7 +266,8 @@ int main(int argc, char **argv) //select_sort(arr, ARR_SIZE); //insrt_sort(arr, ARR_SIZE); //mergesort(arr, 0, ARR_SIZE - 1); - shell_sort(arr, ARR_SIZE); + //shell_sort(arr, ARR_SIZE); + quicksort(0, ARR_SIZE, arr); #ifdef PRINT_FILE fprintf(out, "sorted:\n"); -- cgit v1.2.3