| 1 | /*␊ |
| 2 | * qsort.c␊ |
| 3 | *␊ |
| 4 | * This is actually combsort. It's an O(n log n) algorithm with␊ |
| 5 | * simplicity/small code size being its main virtue.␊ |
| 6 | */␊ |
| 7 | ␊ |
| 8 | #include <stddef.h>␊ |
| 9 | #include <stdlib.h>␊ |
| 10 | #include <string.h>␊ |
| 11 | ␊ |
| 12 | extern void memswap(void *m1, void *m2, size_t n);␊ |
| 13 | ␊ |
| 14 | static inline size_t newgap(size_t gap)␊ |
| 15 | {␊ |
| 16 | ␉gap = (gap * 10) / 13;␊ |
| 17 | ␉if (gap == 9 || gap == 10)␊ |
| 18 | ␉␉gap = 11;␊ |
| 19 | ␊ |
| 20 | ␉if (gap < 1)␊ |
| 21 | ␉␉gap = 1;␊ |
| 22 | ␉return gap;␊ |
| 23 | }␊ |
| 24 | ␊ |
| 25 | void qsort(void *base, size_t nmemb, size_t size,␊ |
| 26 | ␉ int (*compar) (const void *, const void *))␊ |
| 27 | {␊ |
| 28 | ␉size_t gap = nmemb;␊ |
| 29 | ␉size_t i, j;␊ |
| 30 | ␉char *p1, *p2;␊ |
| 31 | ␉int swapped;␊ |
| 32 | ␊ |
| 33 | ␉if (!nmemb)␊ |
| 34 | ␉␉return;␊ |
| 35 | ␊ |
| 36 | ␉do {␊ |
| 37 | ␉␉gap = newgap(gap);␊ |
| 38 | ␉␉swapped = 0;␊ |
| 39 | ␊ |
| 40 | ␉␉for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {␊ |
| 41 | ␉␉␉j = i + gap;␊ |
| 42 | ␉␉␉if (compar(p1, p2 = (char *)base + j * size) > 0) {␊ |
| 43 | ␉␉␉␉memswap(p1, p2, size);␊ |
| 44 | ␉␉␉␉swapped = 1;␊ |
| 45 | ␉␉␉}␊ |
| 46 | ␉␉}␊ |
| 47 | ␉} while (gap > 1 || swapped);␊ |
| 48 | }␊ |
| 49 | |
