1 /*-
2 * Copyright (c) 1980, 1983, 1990 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 #if defined(LIBC_SCCS) && !defined(lint)
35 static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91";
36 #endif /* LIBC_SCCS and not lint */
37
38 #include <sys/types.h>
39 #include <stdlib.h>
40
41 /*
42 * MTHRESH is the smallest partition for which we compare for a median
43 * value instead of using the middle value.
44 */
45 #define MTHRESH 6
46
47 /*
48 * THRESH is the minimum number of entries in a partition for continued
49 * partitioning.
50 */
51 #define THRESH 4
52
53 void
qsort(bot,nmemb,size,compar)54 qsort(bot, nmemb, size, compar)
55 void *bot;
56 size_t nmemb, size;
57 int (*compar) __P((const void *, const void *));
58 {
59 static void insertion_sort(), quick_sort();
60
61 if (nmemb <= 1)
62 return;
63
64 if (nmemb >= THRESH)
65 quick_sort(bot, nmemb, size, compar);
66 else
67 insertion_sort(bot, nmemb, size, compar);
68 }
69
70 /*
71 * Swap two areas of size number of bytes. Although qsort(3) permits random
72 * blocks of memory to be sorted, sorting pointers is almost certainly the
73 * common case (and, were it not, could easily be made so). Regardless, it
74 * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
75 * arithmetic gets lost in the time required for comparison function calls.
76 */
77 #define SWAP(a, b) { \
78 cnt = size; \
79 do { \
80 ch = *a; \
81 *a++ = *b; \
82 *b++ = ch; \
83 } while (--cnt); \
84 }
85
86 /*
87 * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass
88 * of straight insertion sort after partitioning is complete is better than
89 * sorting each small partition as it is created. This isn't correct in this
90 * implementation because comparisons require at least one (and often two)
91 * function calls and are likely to be the dominating expense of the sort.
92 * Doing a final insertion sort does more comparisons than are necessary
93 * because it compares the "edges" and medians of the partitions which are
94 * known to be already sorted.
95 *
96 * This is also the reasoning behind selecting a small THRESH value (see
97 * Knuth, page 122, equation 26), since the quicksort algorithm does less
98 * comparisons than the insertion sort.
99 */
100 #define SORT(bot, n) { \
101 if (n > 1) \
102 if (n == 2) { \
103 t1 = bot + size; \
104 if (compar(t1, bot) < 0) \
105 SWAP(t1, bot); \
106 } else \
107 insertion_sort(bot, n, size, compar); \
108 }
109
110 static void
quick_sort(bot,nmemb,size,compar)111 quick_sort(bot, nmemb, size, compar)
112 register char *bot;
113 register int size;
114 int nmemb, (*compar)();
115 {
116 register int cnt;
117 register u_char ch;
118 register char *top, *mid, *t1, *t2;
119 register int n1, n2;
120 char *bsv;
121 static void insertion_sort();
122
123 /* bot and nmemb must already be set. */
124 partition:
125
126 /* find mid and top elements */
127 mid = bot + size * (nmemb >> 1);
128 top = bot + (nmemb - 1) * size;
129
130 /*
131 * Find the median of the first, last and middle element (see Knuth,
132 * Vol. 3, page 123, Eq. 28). This test order gets the equalities
133 * right.
134 */
135 if (nmemb >= MTHRESH) {
136 n1 = compar(bot, mid);
137 n2 = compar(mid, top);
138 if (n1 < 0 && n2 > 0)
139 t1 = compar(bot, top) < 0 ? top : bot;
140 else if (n1 > 0 && n2 < 0)
141 t1 = compar(bot, top) > 0 ? top : bot;
142 else
143 t1 = mid;
144
145 /* if mid element not selected, swap selection there */
146 if (t1 != mid) {
147 SWAP(t1, mid);
148 mid -= size;
149 }
150 }
151
152 /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
153 #define didswap n1
154 #define newbot t1
155 #define replace t2
156 didswap = 0;
157 for (bsv = bot;;) {
158 for (; bot < mid && compar(bot, mid) <= 0; bot += size);
159 while (top > mid) {
160 if (compar(mid, top) <= 0) {
161 top -= size;
162 continue;
163 }
164 newbot = bot + size; /* value of bot after swap */
165 if (bot == mid) /* top <-> mid, mid == top */
166 replace = mid = top;
167 else { /* bot <-> top */
168 replace = top;
169 top -= size;
170 }
171 goto swap;
172 }
173 if (bot == mid)
174 break;
175
176 /* bot <-> mid, mid == bot */
177 replace = mid;
178 newbot = mid = bot; /* value of bot after swap */
179 top -= size;
180
181 swap: SWAP(bot, replace);
182 bot = newbot;
183 didswap = 1;
184 }
185
186 /*
187 * Quicksort behaves badly in the presence of data which is already
188 * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
189 * To avoid this worst case behavior, if a re-partitioning occurs
190 * without swapping any elements, it is not further partitioned and
191 * is insert sorted. This wins big with almost sorted data sets and
192 * only loses if the data set is very strangely partitioned. A fix
193 * for those data sets would be to return prematurely if the insertion
194 * sort routine is forced to make an excessive number of swaps, and
195 * continue the partitioning.
196 */
197 if (!didswap) {
198 insertion_sort(bsv, nmemb, size, compar);
199 return;
200 }
201
202 /*
203 * Re-partition or sort as necessary. Note that the mid element
204 * itself is correctly positioned and can be ignored.
205 */
206 #define nlower n1
207 #define nupper n2
208 bot = bsv;
209 nlower = (mid - bot) / size; /* size of lower partition */
210 mid += size;
211 nupper = nmemb - nlower - 1; /* size of upper partition */
212
213 /*
214 * If must call recursively, do it on the smaller partition; this
215 * bounds the stack to lg N entries.
216 */
217 if (nlower > nupper) {
218 if (nupper >= THRESH)
219 quick_sort(mid, nupper, size, compar);
220 else {
221 SORT(mid, nupper);
222 if (nlower < THRESH) {
223 SORT(bot, nlower);
224 return;
225 }
226 }
227 nmemb = nlower;
228 } else {
229 if (nlower >= THRESH)
230 quick_sort(bot, nlower, size, compar);
231 else {
232 SORT(bot, nlower);
233 if (nupper < THRESH) {
234 SORT(mid, nupper);
235 return;
236 }
237 }
238 bot = mid;
239 nmemb = nupper;
240 }
241 goto partition;
242 /* NOTREACHED */
243 }
244
245 static void
insertion_sort(bot,nmemb,size,compar)246 insertion_sort(bot, nmemb, size, compar)
247 char *bot;
248 register int size;
249 int nmemb, (*compar)();
250 {
251 register int cnt;
252 register u_char ch;
253 register char *s1, *s2, *t1, *t2, *top;
254
255 /*
256 * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm
257 * S). Insertion sort has the same worst case as most simple sorts
258 * (O N^2). It gets used here because it is (O N) in the case of
259 * sorted data.
260 */
261 top = bot + nmemb * size;
262 for (t1 = bot + size; t1 < top;) {
263 for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;);
264 if (t1 != (t2 += size)) {
265 /* Bubble bytes up through each element. */
266 for (cnt = size; cnt--; ++t1) {
267 ch = *t1;
268 for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2)
269 *s1 = *s2;
270 *s1 = ch;
271 }
272 } else
273 t1 += size;
274 }
275 }
276