1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
/*
* qsort -- simple quicksort
*/
#include <u.h>
typedef
struct
{
int (*cmp)(void*, void*);
void (*swap)(char*, char*, long);
long es;
} Sort;
static void
swapb(char *i, char *j, long es)
{
char c;
do {
c = *i;
*i++ = *j;
*j++ = c;
es--;
} while(es != 0);
}
static void
swapi(char *ii, char *ij, long es)
{
long *i, *j, c;
i = (long*)ii;
j = (long*)ij;
do {
c = *i;
*i++ = *j;
*j++ = c;
es -= sizeof(long);
} while(es != 0);
}
static char*
pivot(char *a, long n, Sort *p)
{
long j;
char *pi, *pj, *pk;
j = n/6 * p->es;
pi = a + j; /* 1/6 */
j += j;
pj = pi + j; /* 1/2 */
pk = pj + j; /* 5/6 */
if(p->cmp(pi, pj) < 0) {
if(p->cmp(pi, pk) < 0) {
if(p->cmp(pj, pk) < 0)
return pj;
return pk;
}
return pi;
}
if(p->cmp(pj, pk) < 0) {
if(p->cmp(pi, pk) < 0)
return pi;
return pk;
}
return pj;
}
static void
qsorts(char *a, long n, Sort *p)
{
long j, es;
char *pi, *pj, *pn;
es = p->es;
while(n > 1) {
if(n > 10) {
pi = pivot(a, n, p);
} else
pi = a + (n>>1)*es;
p->swap(a, pi, es);
pi = a;
pn = a + n*es;
pj = pn;
for(;;) {
do
pi += es;
while(pi < pn && p->cmp(pi, a) < 0);
do
pj -= es;
while(pj > a && p->cmp(pj, a) > 0);
if(pj < pi)
break;
p->swap(pi, pj, es);
}
p->swap(a, pj, es);
j = (pj - a) / es;
n = n-j-1;
if(j >= n) {
qsorts(a, j, p);
a += (j+1)*es;
} else {
qsorts(a + (j+1)*es, n, p);
n = j;
}
}
}
void
qsort(void *va, long n, long es, int (*cmp)(void*, void*))
{
Sort s;
s.cmp = cmp;
s.es = es;
s.swap = swapi;
if(((uintptr)va | es) % sizeof(long))
s.swap = swapb;
qsorts((char*)va, n, &s);
}
|
