implement quicksort

1 files 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 <string.h>
 #include <time.h>
 #include <assert.h>
-#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");