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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
/*
* qsort.c:
* Our own version of the system qsort routine which is faster by an average
* of 25%, with lows and highs of 10% and 50%.
* The THRESHold below is the insertion sort threshold, and has been adjusted
* for records of size 48 bytes.
* The MTHREShold is where we stop finding a better median.
*/
#define THRESH 4 /* threshold for insertion */
#define MTHRESH 6 /* threshold for median */
static int qsz; /* size of each record */
static int (*qcmp)(); /* the comparison routine */
static int thresh; /* THRESHold in chars */
static int mthresh; /* MTHRESHold in chars */
/*
* qsort:
* First, set up some global parameters for qst to share. Then, quicksort
* with qst(), and then a cleanup insertion sort ourselves. Sound simple?
* It's not...
*/
qsort (base, n, size, compar)
char *base;
int n;
int size;
int (*compar)();
{
register char *i, *j, *lo, *hi, *min;
register int c;
char *max;
if (n <= 1) return;
qsz = size;
qcmp = compar;
thresh = qsz*THRESH;
mthresh = qsz*MTHRESH;
max = base + n*qsz;
if (n >= THRESH)
{
qst (base, max);
hi = base + thresh;
}
else
{
hi = max;
}
/*
* First put smallest element, which must be in the first THRESH, in
* the first position as a sentinel. This is done just by searching
* the first THRESH elements (or the first n if n < THRESH), finding
* the min, and swapping it into the first position.
*/
for (j = lo = base; (lo += qsz) < hi; )
{
if ((*qcmp) (j, lo) > 0)
j = lo;
}
if (j != base)
{ /* swap j into place */
for (i = base, hi = base + qsz; i < hi;)
{
c = *j;
*j++ = *i;
*i++ = c;
}
}
/*
* With our sentinel in place, we now run the following hyper-fast
* insertion sort. For each remaining element, min, from [1] to [n-1],
* set hi to the index of the element AFTER which this one goes.
* Then, do the standard insertion sort shift on a character at a time
* basis for each element in the frob.
*/
for (min = base; (hi = min += qsz) < max;)
{
while ( (*qcmp) (hi -= qsz, min) > 0);
if ((hi += qsz) != min)
{
for (lo = min + qsz; --lo >= min;)
{
c = *lo;
for (i = j = lo; (j -= qsz) >= hi; i = j)
*i = *j;
*i = c;
}
}
}
}
/*
* qst:
* Do a quicksort
* First, find the median element, and put that one in the first place as the
* discriminator. (This "median" is just the median of the first, last and
* middle elements). (Using this median instead of the first element is a big
* win). Then, the usual partitioning/swapping, followed by moving the
* discriminator into the right place. Then, figure out the sizes of the two
* partions, do the smaller one recursively and the larger one via a repeat of
* this code. Stopping when there are less than THRESH elements in a partition
* and cleaning up with an insertion sort (in our caller) is a huge win.
* All data swaps are done in-line, which is space-losing but time-saving.
* (And there are only three places where this is done).
*/
qst (base, max)
char *base, *max;
{
register char *i, *j, *jj, *mid;
register int ii, c;
char *tmp;
int lo, hi;
lo = max - base; /* number of elements as chars */
do
{
/*
* At the top here, lo is the number of characters of elements in the
* current partition. (Which should be max - base).
* Find the median of the first, last, and middle element and make that the
* middle element. Set j to largest of first and middle. If max is larger
* than that guy, then it's that guy, else compare max with loser of first
* and take larger. Things are set up to prefer the middle, then the first
* in case of ties.
*/
mid = i = base + qsz * ((lo/qsz) >> 1);
if (lo >= mthresh)
{
j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
if ((*qcmp) (j, (tmp = max - qsz)) > 0)
{
j = (j == jj ? i : jj); /* switch to first loser */
if ((*qcmp) (j, tmp) < 0)
j = tmp;
}
if (j != i)
{
ii = qsz;
do
{
c = *i;
*i++ = *j;
*j++ = c;
}
while( --ii );
}
}
/*
* Semi-standard quicksort partitioning/swapping
*/
for (i = base, j = max - qsz; ;)
{
while (i < mid && (*qcmp) (i, mid) <= 0)
i += qsz;
while (j > mid)
{
if ((*qcmp) (mid, j) <= 0)
{
j -= qsz;
continue;
}
tmp = i + qsz; /* value of i after swap */
if (i == mid)
{ /* j <-> mid, new mid is j */
mid = jj = j;
}
else
{ /* i <-> j */
jj = j;
j -= qsz;
}
goto swap;
}
if (i == mid)
{
break;
}
else
{ /* i <-> mid, new mid is i */
jj = mid;
tmp = mid = i; /* value of i after swap */
j -= qsz;
}
swap:
ii = qsz;
do
{
c = *i;
*i++ = *jj;
*jj++ = c;
}
while (--ii);
i = tmp;
}
/*
* Look at sizes of the two partitions, do the smaller one first by
* recursion, then do the larger one by making sure lo is its size,
* base and max are update correctly, and branching back.
* But only repeat (recursively or by branching) if the partition is
* of at least size THRESH.
*/
i = (j = mid) + qsz;
if ((lo = j - base) <= (hi = max - i))
{
if (lo >= thresh)
qst (base, j);
base = i;
lo = hi;
}
else
{
if (hi >= thresh)
qst (i, max);
max = j;
}
}
while (lo >= thresh);
}
|
