diff options
| -rw-r--r-- | musl_heapsort.c | 37 | ||||
| -rw-r--r-- | musl_smoothsort.c (renamed from musl_qsort.c) | 2 | ||||
| -rw-r--r-- | sorters.c | 3 |
3 files changed, 40 insertions, 2 deletions
diff --git a/musl_heapsort.c b/musl_heapsort.c new file mode 100644 index 0000000..33a72d5 --- /dev/null +++ b/musl_heapsort.c @@ -0,0 +1,37 @@ +#include <stdlib.h> + +#include "sorters.h" +#include "common.h" + +/* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */ + +#define MIN(a, b) ((a)<(b) ? (a) : (b)) + +static void sift(char *base, size_t root, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + size_t max; + + while (2*root <= nel) { + max = 2*root; + if (max < nel && cmp(base+max*width, base+(max+1)*width) < 0) + max++; + if (max && cmp(base+root*width, base+max*width) < 0) { + swap(base+root*width, base+max*width, width); + root = max; + } else break; + } +} + +void musl_heapsort(void *_base, size_t nel, size_t width, cmpfun cmp) +{ + char *base = _base; + size_t i; + + if (!nel) return; + for (i=(nel+1)/2; i; i--) + sift(base, i-1, nel-1, width, cmp); + for (i=nel-1; i; i--) { + swap(base, base+i*width, width); + sift(base, 0, i-1, width, cmp); + } +} diff --git a/musl_qsort.c b/musl_smoothsort.c index 3792aa1..4a1dfb1 100644 --- a/musl_qsort.c +++ b/musl_smoothsort.c @@ -154,7 +154,7 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], } } -void musl_qsort(void *base, size_t nel, size_t width, cmpfun cmp) +void musl_smoothsort(void *base, size_t nel, size_t width, cmpfun cmp) { size_t lp[12*sizeof(size_t)]; size_t i, size = width * nel; @@ -7,7 +7,8 @@ const struct sorter sorters[] = { { .name = "freebsd", .func = freebsd_qsort }, { .name = "glibc quicksort", .func = glibc_quicksort }, { .name = "glibc mergesort", .func = glibc_mergesort }, - { .name = "musl", .func = musl_qsort }, + { .name = "musl smoothsort", .func = musl_smoothsort }, + { .name = "musl heapsort", .func = musl_heapsort }, { .name = "wikisort", .func = wikisort }, { .name = "wikisort (ref)", .func = wikisort_ref }, { .name = "grailsort", .func = grailsort }, |