Commit | Line | Data |
---|---|---|
b8f253e8 KM |
1 | /* |
2 | * Copyright (c) 1980 Regents of the University of California. | |
3 | * All rights reserved. The Berkeley software License Agreement | |
4 | * specifies the terms and conditions for redistribution. | |
5 | */ | |
6 | ||
2ce81398 DS |
7 | #if defined(LIBC_SCCS) && !defined(lint) |
8 | static char sccsid[] = "@(#)qsort.c 5.2 (Berkeley) %G%"; | |
9 | #endif LIBC_SCCS and not lint | |
b4751583 | 10 | |
6c625db4 KM |
11 | /* |
12 | * qsort.c: | |
13 | * Our own version of the system qsort routine which is faster by an average | |
14 | * of 25%, with lows and highs of 10% and 50%. | |
15 | * The THRESHold below is the insertion sort threshold, and has been adjusted | |
16 | * for records of size 48 bytes. | |
17 | * The MTHREShold is where we stop finding a better median. | |
18 | */ | |
b4751583 | 19 | |
6c625db4 KM |
20 | #define THRESH 4 /* threshold for insertion */ |
21 | #define MTHRESH 6 /* threshold for median */ | |
b4751583 | 22 | |
6c625db4 KM |
23 | static int (*qcmp)(); /* the comparison routine */ |
24 | static int qsz; /* size of each record */ | |
25 | static int thresh; /* THRESHold in chars */ | |
26 | static int mthresh; /* MTHRESHold in chars */ | |
b4751583 | 27 | |
6c625db4 KM |
28 | /* |
29 | * qsort: | |
30 | * First, set up some global parameters for qst to share. Then, quicksort | |
31 | * with qst(), and then a cleanup insertion sort ourselves. Sound simple? | |
32 | * It's not... | |
33 | */ | |
b4751583 | 34 | |
6c625db4 KM |
35 | qsort(base, n, size, compar) |
36 | char *base; | |
37 | int n; | |
38 | int size; | |
39 | int (*compar)(); | |
40 | { | |
41 | register char c, *i, *j, *lo, *hi; | |
42 | char *min, *max; | |
b4751583 | 43 | |
6c625db4 | 44 | if (n <= 1) |
b4751583 | 45 | return; |
6c625db4 KM |
46 | qsz = size; |
47 | qcmp = compar; | |
48 | thresh = qsz * THRESH; | |
49 | mthresh = qsz * MTHRESH; | |
50 | max = base + n * qsz; | |
51 | if (n >= THRESH) { | |
52 | qst(base, max); | |
53 | hi = base + thresh; | |
54 | } else { | |
55 | hi = max; | |
56 | } | |
57 | /* | |
58 | * First put smallest element, which must be in the first THRESH, in | |
59 | * the first position as a sentinel. This is done just by searching | |
60 | * the first THRESH elements (or the first n if n < THRESH), finding | |
61 | * the min, and swapping it into the first position. | |
62 | */ | |
63 | for (j = lo = base; (lo += qsz) < hi; ) | |
64 | if (qcmp(j, lo) > 0) | |
65 | j = lo; | |
66 | if (j != base) { | |
67 | /* swap j into place */ | |
68 | for (i = base, hi = base + qsz; i < hi; ) { | |
69 | c = *j; | |
70 | *j++ = *i; | |
71 | *i++ = c; | |
b4751583 | 72 | } |
6c625db4 KM |
73 | } |
74 | /* | |
75 | * With our sentinel in place, we now run the following hyper-fast | |
76 | * insertion sort. For each remaining element, min, from [1] to [n-1], | |
77 | * set hi to the index of the element AFTER which this one goes. | |
78 | * Then, do the standard insertion sort shift on a character at a time | |
79 | * basis for each element in the frob. | |
80 | */ | |
81 | for (min = base; (hi = min += qsz) < max; ) { | |
82 | while (qcmp(hi -= qsz, min) > 0) | |
83 | /* void */; | |
84 | if ((hi += qsz) != min) { | |
85 | for (lo = min + qsz; --lo >= min; ) { | |
86 | c = *lo; | |
87 | for (i = j = lo; (j -= qsz) >= hi; i = j) | |
88 | *i = *j; | |
89 | *i = c; | |
b4751583 | 90 | } |
b4751583 | 91 | } |
b4751583 BJ |
92 | } |
93 | } | |
94 | ||
6c625db4 KM |
95 | /* |
96 | * qst: | |
97 | * Do a quicksort | |
98 | * First, find the median element, and put that one in the first place as the | |
99 | * discriminator. (This "median" is just the median of the first, last and | |
100 | * middle elements). (Using this median instead of the first element is a big | |
101 | * win). Then, the usual partitioning/swapping, followed by moving the | |
102 | * discriminator into the right place. Then, figure out the sizes of the two | |
103 | * partions, do the smaller one recursively and the larger one via a repeat of | |
104 | * this code. Stopping when there are less than THRESH elements in a partition | |
105 | * and cleaning up with an insertion sort (in our caller) is a huge win. | |
106 | * All data swaps are done in-line, which is space-losing but time-saving. | |
107 | * (And there are only three places where this is done). | |
108 | */ | |
b4751583 | 109 | |
6c625db4 KM |
110 | static |
111 | qst(base, max) | |
112 | char *base, *max; | |
b4751583 | 113 | { |
6c625db4 KM |
114 | register char c, *i, *j, *jj; |
115 | register int ii; | |
116 | char *mid, *tmp; | |
117 | int lo, hi; | |
b4751583 | 118 | |
6c625db4 KM |
119 | /* |
120 | * At the top here, lo is the number of characters of elements in the | |
121 | * current partition. (Which should be max - base). | |
122 | * Find the median of the first, last, and middle element and make | |
123 | * that the middle element. Set j to largest of first and middle. | |
124 | * If max is larger than that guy, then it's that guy, else compare | |
125 | * max with loser of first and take larger. Things are set up to | |
126 | * prefer the middle, then the first in case of ties. | |
127 | */ | |
128 | lo = max - base; /* number of elements as chars */ | |
129 | do { | |
130 | mid = i = base + qsz * ((lo / qsz) >> 1); | |
131 | if (lo >= mthresh) { | |
132 | j = (qcmp((jj = base), i) > 0 ? jj : i); | |
133 | if (qcmp(j, (tmp = max - qsz)) > 0) { | |
134 | /* switch to first loser */ | |
135 | j = (j == jj ? i : jj); | |
136 | if (qcmp(j, tmp) < 0) | |
137 | j = tmp; | |
138 | } | |
139 | if (j != i) { | |
140 | ii = qsz; | |
141 | do { | |
142 | c = *i; | |
143 | *i++ = *j; | |
144 | *j++ = c; | |
145 | } while (--ii); | |
146 | } | |
147 | } | |
148 | /* | |
149 | * Semi-standard quicksort partitioning/swapping | |
150 | */ | |
151 | for (i = base, j = max - qsz; ; ) { | |
152 | while (i < mid && qcmp(i, mid) <= 0) | |
153 | i += qsz; | |
154 | while (j > mid) { | |
155 | if (qcmp(mid, j) <= 0) { | |
156 | j -= qsz; | |
157 | continue; | |
158 | } | |
159 | tmp = i + qsz; /* value of i after swap */ | |
160 | if (i == mid) { | |
161 | /* j <-> mid, new mid is j */ | |
162 | mid = jj = j; | |
163 | } else { | |
164 | /* i <-> j */ | |
165 | jj = j; | |
166 | j -= qsz; | |
167 | } | |
168 | goto swap; | |
169 | } | |
170 | if (i == mid) { | |
171 | break; | |
172 | } else { | |
173 | /* i <-> mid, new mid is i */ | |
174 | jj = mid; | |
175 | tmp = mid = i; /* value of i after swap */ | |
176 | j -= qsz; | |
177 | } | |
178 | swap: | |
179 | ii = qsz; | |
180 | do { | |
181 | c = *i; | |
182 | *i++ = *jj; | |
183 | *jj++ = c; | |
184 | } while (--ii); | |
185 | i = tmp; | |
186 | } | |
187 | /* | |
188 | * Look at sizes of the two partitions, do the smaller | |
189 | * one first by recursion, then do the larger one by | |
190 | * making sure lo is its size, base and max are update | |
191 | * correctly, and branching back. But only repeat | |
192 | * (recursively or by branching) if the partition is | |
193 | * of at least size THRESH. | |
194 | */ | |
195 | i = (j = mid) + qsz; | |
196 | if ((lo = j - base) <= (hi = max - i)) { | |
197 | if (lo >= thresh) | |
198 | qst(base, j); | |
199 | base = i; | |
200 | lo = hi; | |
201 | } else { | |
202 | if (hi >= thresh) | |
203 | qst(i, max); | |
204 | max = j; | |
205 | } | |
206 | } while (lo >= thresh); | |
b4751583 | 207 | } |