diff options
author | Rich Felker <dalias@aerifal.cx> | 2011-02-12 00:22:29 -0500 |
---|---|---|
committer | Rich Felker <dalias@aerifal.cx> | 2011-02-12 00:22:29 -0500 |
commit | 0b44a0315b47dd8eced9f3b7f31580cf14bbfc01 (patch) | |
tree | 6eaef0d8a720fa3da580de87b647fff796fe80b3 /src/stdlib/qsort.c | |
download | musl-0b44a0315b47dd8eced9f3b7f31580cf14bbfc01.tar.gz musl-0b44a0315b47dd8eced9f3b7f31580cf14bbfc01.tar.bz2 musl-0b44a0315b47dd8eced9f3b7f31580cf14bbfc01.tar.xz musl-0b44a0315b47dd8eced9f3b7f31580cf14bbfc01.zip |
initial check-in, version 0.5.0v0.5.0
Diffstat (limited to 'src/stdlib/qsort.c')
-rw-r--r-- | src/stdlib/qsort.c | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c new file mode 100644 index 00000000..f5bf3d02 --- /dev/null +++ b/src/stdlib/qsort.c @@ -0,0 +1,50 @@ +#include <stdlib.h> +#include <string.h> + +/* A simple heap sort implementation.. only in-place O(nlogn) sort I know. */ + +#define MIN(a, b) ((a)<(b) ? (a) : (b)) + +static void swap(char *a, char *b, size_t len) +{ + char tmp[256]; + size_t l; + while (len) { + l = MIN(sizeof tmp, len); + memcpy(tmp, a, l); + memcpy(a, b, l); + memcpy(b, tmp, l); + a += l; + b += l; + len -= l; + } +} + +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 (cmp(base+root*width, base+max*width) < 0) { + swap(base+root*width, base+max*width, width); + root = max; + } else break; + } +} + +void qsort(void *_base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + 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); + } +} |