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