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