1 /* qsort -- qsort interface implemented by faster quicksort */
2 #include <stdlib.h>
3
4 #define SWAPINIT(a, es) swaptype = \
5 (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \
6 es == sizeof(long) ? 0 : 1;
7 #define swapcode(TYPE, parmi, parmj, n) { \
8 long i = (n) / (int) sizeof(TYPE); \
9 register TYPE *pi = (TYPE *) (parmi); \
10 register TYPE *pj = (TYPE *) (parmj); \
11 do { \
12 register TYPE t = *pi; \
13 *pi++ = *pj; \
14 *pj++ = t; \
15 } while (--i > 0); \
16 }
swapfunc(char * a,char * b,int n,int swaptype)17 static void swapfunc(char *a, char *b, int n, int swaptype)
18 { if (swaptype <= 1) swapcode(long, a, b, n)
19 else swapcode(char, a, b, n)
20 }
21 #define swap(a, b) { \
22 if (swaptype == 0) { \
23 long t = * (long *) (a); \
24 * (long *) (a) = * (long *) (b); \
25 * (long *) (b) = t; \
26 } else \
27 swapfunc(a, b, es, swaptype); \
28 }
29 #define vecswap(a, b, n) { if (n > 0) swapfunc(a, b, n*es, swaptype); }
30
med3func(char * a,char * b,char * c,int (* cmp)(const void *,const void *))31 static char *med3func(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
32 { return cmp(a, b) < 0 ?
33 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) )
34 : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) );
35 }
36 #define med3(a, b, c) med3func(a, b, c, cmp)
37
qsort(void * va,size_t n,size_t es,int (* cmp)(const void *,const void *))38 void qsort(void *va, size_t n, size_t es, int (*cmp)(const void *, const void *))
39 {
40 char *a, *pa, *pb, *pc, *pd, *pl, *pm, *pn;
41 int r, swaptype, na, nb, nc, nd, d;
42
43 a = va;
44 SWAPINIT(a, es);
45 if (n < 7) { /* Insertion sort on small arrays */
46 for (pm = a + es; pm < a + n*es; pm += es)
47 for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
48 swap(pl, pl-es);
49 return;
50 }
51 pm = a + (n/2) * es;
52 if (n > 7) {
53 pl = a;
54 pn = a + (n-1) * es;
55 if (n > 40) { /* On big arrays, pseudomedian of 9 */
56 d = (n/8) * es;
57 pl = med3(pl, pl+d, pl+2*d);
58 pm = med3(pm-d, pm, pm+d);
59 pn = med3(pn-2*d, pn-d, pn);
60 }
61 pm = med3(pl, pm, pn); /* On medium arrays, median of 3 */
62 }
63 swap(a, pm); /* On tiny arrays, partition around middle */
64 pa = pb = a + es;
65 pc = pd = pn = a + (n-1)*es;
66 for (;;) {
67 while (pb <= pc && (r = cmp(pb, a)) <= 0) {
68 if (r == 0) { swap(pa, pb); pa += es; }
69 pb += es;
70 }
71 while (pb <= pc && (r = cmp(pc, a)) >= 0) {
72 if (r == 0) { swap(pc, pd); pd -= es; }
73 pc -= es;
74 }
75 if (pb > pc) break;
76 swap(pb, pc);
77 pb += es;
78 pc -= es;
79 }
80 na = (pa - a) / es;
81 nb = (pb - pa) / es;
82 nc = (pd - pc) / es;
83 nd = (pn - pd) / es;
84 if (na < nb) { vecswap(a, a + nb*es, na); }
85 else { vecswap(a, a + na*es, nb); }
86 if (nc < nd) { vecswap(pb, pb + nd*es, nc); }
87 else { vecswap(pb, pb + nc*es, nd); }
88 if (nb > 1) qsort(a, nb, es, cmp);
89 if (nc > 1) qsort(a + (n-nc) * es, nc, es, cmp);
90 }
91