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
newgap(size_t gap)12 static inline size_t newgap(size_t gap)
13 {
14 gap = (gap * 10) / 13;
15 if (gap == 9 || gap == 10)
16 gap = 11;
17
18 if (gap < 1)
19 gap = 1;
20 return gap;
21 }
22
qsort(void * base,size_t nmemb,size_t size,int (* compar)(const void *,const void *))23 void qsort(void *base, size_t nmemb, size_t size,
24 int (*compar) (const void *, const void *))
25 {
26 size_t gap = nmemb;
27 size_t i, j;
28 char *p1, *p2;
29 int swapped;
30
31 if (!nmemb)
32 return;
33
34 do {
35 gap = newgap(gap);
36 swapped = 0;
37
38 for (i = 0, p1 = base; i < nmemb - gap; i++, p1 += size) {
39 j = i + gap;
40 if (compar(p1, p2 = (char *)base + j * size) > 0) {
41 memswap(p1, p2, size);
42 swapped = 1;
43 }
44 }
45 } while (gap > 1 || swapped);
46 }
47