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