test/sort.c

1 files changed, 31 insertions, 0 deletions

diff --git a/test/sort.c b/test/sort.c
index af58917..8507cb2 100644
--- a/test/sort.c
+++ b/test/sort.c
@@ -12,6 +12,32 @@ icmp(const void *a, const void *b)
    return (l > r) - (l < r);
 }
 
+int nswp = 0, ncmp = 0;
+void
+revsort(int *xs, long lo, long hi)
+{
+   while (lo < hi) {
+      long i = lo - 1, p = hi + 1;
+      int pivot = xs[lo], tmp;
+      for (;;) {
+         do ++i; while (++ncmp, xs[i] > pivot);
+         do --p; while (++ncmp, xs[p] < pivot);
+         if (i >= p) break;
+         tmp = xs[i];
+         xs[i] = xs[p];
+         xs[p] = tmp;
+         ++nswp;
+      }
+      if (p + 1 >= hi) {
+         hi = p;
+      } else {
+         if (lo < p)
+            revsort(xs, lo, p);
+         lo = p + 1;
+      }
+   }
+}
+
 int
 main(int argc, char **argv)
 {
@@ -24,5 +50,10 @@ main(int argc, char **argv)
    for (int i = 0; i < N; ++i)
       printf("%d, ", xs[i]);
    printf("\n");
+   revsort(xs, 0,N-1);
+   printf("%d cmps, %d swaps\n", ncmp, nswp);
+   for (int i = 0; i < N; ++i)
+      printf("%d, ", xs[i]);
+   printf("\n");
    return N;
 }