sort.c
changeset 73 d0578510aea1
parent 72 4103c76d5bf2
child 74 829976007e62
--- a/sort.c
+++ b/sort.c
@@ -95,12 +95,56 @@
     statistic ("Bubble");
 }
 
+static int divide (int *v, int left, int right)
+{
+    int i, j, pivot;
+
+    i = left;
+    j = right - 1;
+
+    pivot = v[right];
+
+    do {
+        while (v[i] <= pivot && i < right) {
+            iters++;
+            i++;
+        }
+        while (v[j] >= pivot && j > left) {
+            iters++;
+            j--;
+        }
+        if (i < j) {
+            counter++;
+            swap (v, i, j);
+        }
+
+        if (v[i] > pivot) {
+            counter++;
+            swap (v, i, right);
+        }
+    } while (i < j);
+
+    return i;
+}
+
+void quicksort (int *v, int left, int right)
+{
+    int divisor;
+
+    if (left < right) {
+        divisor = divide (v, left, right);
+        quicksort (v, left, divisor - 1);
+        quicksort (v, divisor + 1, right);
+    }
+}
+
 int main (int argc, char **argv)
 {
     int a[MAX];
     int b[MAX];
     int c[MAX];
     int d[MAX];
+    int e[MAX];
 
     int i;
 
@@ -113,20 +157,24 @@
     memcpy (b, a, sizeof (a));
     memcpy (c, a, sizeof (a));
     memcpy (d, a, sizeof (a));
+    memcpy (e, a, sizeof (a));
 
     lazysort (a, MAX, &compare);
     linearsort (b, MAX, &compare);
     bubblesort (c, MAX, &compare);
 
-    qsort (d, MAX, sizeof (int), (void *)&compare);
-    statistic ("Quick");
+    quicksort (d, 0, MAX - 1);
+    statistic ("mquick");
+
+    qsort (e, MAX, sizeof (int), (void *)&compare);
+    statistic ("gquick");
 
     printf ("PRESS <RETURN> to CONTINUE");
-    while (getchar () != 10);
-    printf ("%2c %2c %2c %2c\n-----------\n", 'L', 'N', 'B', 'Q');
+    while (getchar () != '\n');
 
+    printf ("%6c %6c %6c %6c %6c\n----------------------------------\n", 'L', 'N', 'B', 'M', 'G');
     for (i = 0; i < MAX; i++)
-        printf ("%2d %2d %2d %2d\n", a[i], b[i], c[i], d[i]);
+        printf ("%6d %6d %6d %6d %6d\n", a[i], b[i], c[i], d[i], e[i]);
 
     return EXIT_SUCCESS;
 }