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 | |