ref: 428e86f306625a3192e03260a921a19c3109f57d
parent: bb99c8599bac91bd98e0f9bbe0c994e97f0956a1
author: Roberto E. Vargas Caballero <[email protected]>
date: Thu Dec 7 20:14:36 EST 2017
[lib/c] Add qsort()
--- a/lib/c/src/Makefile
+++ b/lib/c/src/Makefile
@@ -2,7 +2,7 @@
include ../../../config.mk
-OBJ = bsearch.o \
+OBJ = bsearch.o qsort.o \
abs.o __abs.o labs.o __labs.o llabs.o __labs.o \
perror.o strerror.o \
printf.o fprintf.o vfprintf.o \
--- /dev/null
+++ b/lib/c/src/qsort.c
@@ -1,0 +1,155 @@
+
+#include <stdlib.h>
+#include <string.h>
+#undef qsort
+
+/*
+ * This implementation of qsort is based in the paper
+ * "Engineering a Sort Function", by Jon L.Bentley and M. Douglas McIlroy
+ */
+
+struct qsort {+ size_t es;
+ int (*cmp)(const void *, const void *);
+ void (*swap)(char *i, char *j, size_t n);
+};
+
+static void
+swapb(char *i, char *j, size_t n)
+{+ do {+ char c = *i;
+ *i++ = *j;
+ *j++ = c;
+ } while (--n > 0);
+}
+
+static void
+swapw(char *i, char *j, size_t n)
+{+ int w, *wi = (int *) i, *wj = (int *) j;
+
+ n /= sizeof(w);
+
+ do {+ w = *wi;
+ *wi++ = *wj;
+ *wj++ = w;
+ } while (--n > 0);
+}
+
+static void
+swapl(char *i, char *j, size_t n)
+{+ char *tmp[n];
+
+ memcpy(tmp, i, n);
+ memcpy(i, j, n);
+ memcpy(j, tmp, n);
+}
+
+static char *
+med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
+{+ if (cmp(a, b) < 0) {+ if (cmp(b, c) < 0)
+ return b;
+ return (cmp(a, c) < 0) ? c : a;
+ } else {+ if (cmp(b, c) > 0)
+ return b;
+ return (cmp(a, c) > 0) ? c : a;
+ }
+}
+
+static char *
+pivot(char *v, size_t n, struct qsort *qs)
+{+ char *p1, *pm, *pn; /* 1st, middle, nth */
+ int (*cmp)(const void *, const void *);
+ size_t s, es = qs->es;
+
+
+ pm = v + n/2 * es;
+ if (n < 10)
+ return pm;
+
+ cmp = qs->cmp;
+ s = n/6 * es;
+ p1 = v + s;
+ pn = pm + 2*s;
+
+ if (n > 50) {+ s = n/8 * es;
+ p1 = med3(p1, p1+s, p1 + 2*s, cmp);
+ pm = med3(pm-s, pm, pm+s, cmp);
+ pn = med3(pn-2*s, pn-s, pn, cmp);
+ }
+
+ return med3(p1, pm, pn, qs->cmp);
+}
+
+static void
+xqsort(char *a, size_t n, struct qsort *qs)
+{+ size_t j, es = qs->es;
+ char *pi, *pj, *pn;
+
+tail_recursion:
+ if (n <= 1)
+ return;
+
+ pi = a;
+ pn = pj = a + n*es;
+
+ qs->swap(a, pivot(a, n, qs), es);
+ for (;;) {+ do {+ pi += es;
+ } while (pi < pn && qs->cmp(pi, pn) < 0);
+
+ do {+ pj -= es;
+ } while (pj > a && qs->cmp(pj, a) > 0);
+
+ if (pj < pi)
+ break;
+ qs->swap(pi, pj, es);
+ }
+ qs->swap(a, pj, es);
+
+ /*
+ * We have to recurse over two subarrays. One of them can be
+ * optimized with tail recursion. We select to recurse over
+ * the bigger subarray, because it will allow us to apply a
+ * better divide and conquer strategy.
+ */
+ j = (pj - a) / es;
+ if (j >= n) {+ xqsort(a, j, qs);
+ a += (j+1) * es;
+ } else {+ xqsort(a + (j+1) * es, n-j-1, qs);
+ n = j;
+ }
+ goto tail_recursion;
+}
+
+void
+qsort(void *base, size_t nmemb, size_t size,
+ int (*f)(const void *, const void *))
+{+ struct qsort qs;
+
+ qs.cmp = f;
+ qs.es = size;
+
+ if (size > 7 * sizeof(int))
+ qs.swap = swapl;
+ else if (size % sizeof(int) == 0)
+ qs.swap = swapw;
+ else
+ qs.swap = swapb;
+
+ xqsort(base, nmemb, &qs);
+}