Commit | Line | Data |
---|---|---|
c49eef45 | 1 | /*- |
6e0cb3ec | 2 | * Copyright (c) 1980, 1983, 1990 The Regents of the University of California. |
202a4bd9 KB |
3 | * All rights reserved. |
4 | * | |
c49eef45 | 5 | * %sccs.include.redist.c% |
b8f253e8 KM |
6 | */ |
7 | ||
2ce81398 | 8 | #if defined(LIBC_SCCS) && !defined(lint) |
f0a345ab | 9 | static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) %G%"; |
202a4bd9 | 10 | #endif /* LIBC_SCCS and not lint */ |
b4751583 | 11 | |
6e0cb3ec | 12 | #include <sys/types.h> |
f0a345ab | 13 | #include <stdlib.h> |
dd967b02 | 14 | |
6c625db4 | 15 | /* |
6e0cb3ec KB |
16 | * MTHRESH is the smallest partition for which we compare for a median |
17 | * value instead of using the middle value. | |
6c625db4 | 18 | */ |
6e0cb3ec | 19 | #define MTHRESH 6 |
b4751583 | 20 | |
6c625db4 | 21 | /* |
6e0cb3ec KB |
22 | * THRESH is the minimum number of entries in a partition for continued |
23 | * partitioning. | |
6c625db4 | 24 | */ |
6e0cb3ec | 25 | #define THRESH 4 |
b4751583 | 26 | |
753a5bae | 27 | void |
6e0cb3ec | 28 | qsort(bot, nmemb, size, compar) |
f0a345ab DS |
29 | void *bot; |
30 | size_t nmemb, size; | |
31 | int (*compar) __P((const void *, const void *)); | |
6c625db4 | 32 | { |
f0a345ab | 33 | static void insertion_sort(), quick_sort(); |
b4751583 | 34 | |
6e0cb3ec | 35 | if (nmemb <= 1) |
b4751583 | 36 | return; |
6e0cb3ec KB |
37 | |
38 | if (nmemb >= THRESH) | |
39 | quick_sort(bot, nmemb, size, compar); | |
40 | else | |
41 | insertion_sort(bot, nmemb, size, compar); | |
42 | } | |
43 | ||
44 | /* | |
45 | * Swap two areas of size number of bytes. Although qsort(3) permits random | |
46 | * blocks of memory to be sorted, sorting pointers is almost certainly the | |
47 | * common case (and, were it not, could easily be made so). Regardless, it | |
48 | * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer | |
49 | * arithmetic gets lost in the time required for comparison function calls. | |
50 | */ | |
51 | #define SWAP(a, b) { \ | |
52 | cnt = size; \ | |
53 | do { \ | |
54 | ch = *a; \ | |
55 | *a++ = *b; \ | |
56 | *b++ = ch; \ | |
57 | } while (--cnt); \ | |
58 | } | |
59 | ||
60 | /* | |
61 | * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass | |
62 | * of straight insertion sort after partitioning is complete is better than | |
63 | * sorting each small partition as it is created. This isn't correct in this | |
64 | * implementation because comparisons require at least one (and often two) | |
65 | * function calls and are likely to be the dominating expense of the sort. | |
66 | * Doing a final insertion sort does more comparisons than are necessary | |
67 | * because it compares the "edges" and medians of the partitions which are | |
68 | * known to be already sorted. | |
69 | * | |
70 | * This is also the reasoning behind selecting a small THRESH value (see | |
71 | * Knuth, page 122, equation 26), since the quicksort algorithm does less | |
72 | * comparisons than the insertion sort. | |
73 | */ | |
74 | #define SORT(bot, n) { \ | |
75 | if (n > 1) \ | |
76 | if (n == 2) { \ | |
77 | t1 = bot + size; \ | |
78 | if (compar(t1, bot) < 0) \ | |
79 | SWAP(t1, bot); \ | |
80 | } else \ | |
81 | insertion_sort(bot, n, size, compar); \ | |
82 | } | |
83 | ||
84 | static void | |
85 | quick_sort(bot, nmemb, size, compar) | |
86 | register char *bot; | |
87 | register int size; | |
88 | int nmemb, (*compar)(); | |
89 | { | |
90 | register int cnt; | |
91 | register u_char ch; | |
92 | register char *top, *mid, *t1, *t2; | |
93 | register int n1, n2; | |
94 | char *bsv; | |
f0a345ab | 95 | static void insertion_sort(); |
6e0cb3ec KB |
96 | |
97 | /* bot and nmemb must already be set. */ | |
98 | partition: | |
99 | ||
100 | /* find mid and top elements */ | |
101 | mid = bot + size * (nmemb >> 1); | |
102 | top = bot + (nmemb - 1) * size; | |
103 | ||
6c625db4 | 104 | /* |
6e0cb3ec KB |
105 | * Find the median of the first, last and middle element (see Knuth, |
106 | * Vol. 3, page 123, Eq. 28). This test order gets the equalities | |
107 | * right. | |
6c625db4 | 108 | */ |
6e0cb3ec KB |
109 | if (nmemb >= MTHRESH) { |
110 | n1 = compar(bot, mid); | |
111 | n2 = compar(mid, top); | |
112 | if (n1 < 0 && n2 > 0) | |
113 | t1 = compar(bot, top) < 0 ? top : bot; | |
114 | else if (n1 > 0 && n2 < 0) | |
115 | t1 = compar(bot, top) > 0 ? top : bot; | |
116 | else | |
117 | t1 = mid; | |
118 | ||
119 | /* if mid element not selected, swap selection there */ | |
120 | if (t1 != mid) { | |
121 | SWAP(t1, mid); | |
122 | mid -= size; | |
b4751583 | 123 | } |
6c625db4 | 124 | } |
6e0cb3ec KB |
125 | |
126 | /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */ | |
127 | #define didswap n1 | |
128 | #define newbot t1 | |
129 | #define replace t2 | |
130 | didswap = 0; | |
131 | for (bsv = bot;;) { | |
132 | for (; bot < mid && compar(bot, mid) <= 0; bot += size); | |
133 | while (top > mid) { | |
134 | if (compar(mid, top) <= 0) { | |
135 | top -= size; | |
136 | continue; | |
137 | } | |
138 | newbot = bot + size; /* value of bot after swap */ | |
139 | if (bot == mid) /* top <-> mid, mid == top */ | |
140 | replace = mid = top; | |
141 | else { /* bot <-> top */ | |
142 | replace = top; | |
143 | top -= size; | |
b4751583 | 144 | } |
6e0cb3ec | 145 | goto swap; |
b4751583 | 146 | } |
6e0cb3ec KB |
147 | if (bot == mid) |
148 | break; | |
149 | ||
150 | /* bot <-> mid, mid == bot */ | |
151 | replace = mid; | |
152 | newbot = mid = bot; /* value of bot after swap */ | |
153 | top -= size; | |
154 | ||
155 | swap: SWAP(bot, replace); | |
156 | bot = newbot; | |
157 | didswap = 1; | |
b4751583 | 158 | } |
b4751583 | 159 | |
6e0cb3ec KB |
160 | /* |
161 | * Quicksort behaves badly in the presence of data which is already | |
162 | * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2. | |
163 | * To avoid this worst case behavior, if a re-partitioning occurs | |
164 | * without swapping any elements, it is not further partitioned and | |
165 | * is insert sorted. This wins big with almost sorted data sets and | |
166 | * only loses if the data set is very strangely partitioned. A fix | |
167 | * for those data sets would be to return prematurely if the insertion | |
168 | * sort routine is forced to make an excessive number of swaps, and | |
169 | * continue the partitioning. | |
170 | */ | |
171 | if (!didswap) { | |
172 | insertion_sort(bsv, nmemb, size, compar); | |
173 | return; | |
174 | } | |
b4751583 | 175 | |
6e0cb3ec KB |
176 | /* |
177 | * Re-partition or sort as necessary. Note that the mid element | |
178 | * itself is correctly positioned and can be ignored. | |
179 | */ | |
180 | #define nlower n1 | |
181 | #define nupper n2 | |
182 | bot = bsv; | |
183 | nlower = (mid - bot) / size; /* size of lower partition */ | |
184 | mid += size; | |
185 | nupper = nmemb - nlower - 1; /* size of upper partition */ | |
b4751583 | 186 | |
6c625db4 | 187 | /* |
6e0cb3ec KB |
188 | * If must call recursively, do it on the smaller partition; this |
189 | * bounds the stack to lg N entries. | |
6c625db4 | 190 | */ |
6e0cb3ec KB |
191 | if (nlower > nupper) { |
192 | if (nupper >= THRESH) | |
193 | quick_sort(mid, nupper, size, compar); | |
194 | else { | |
195 | SORT(mid, nupper); | |
196 | if (nlower < THRESH) { | |
197 | SORT(bot, nlower); | |
198 | return; | |
6c625db4 KM |
199 | } |
200 | } | |
6e0cb3ec KB |
201 | nmemb = nlower; |
202 | } else { | |
203 | if (nlower >= THRESH) | |
204 | quick_sort(bot, nlower, size, compar); | |
205 | else { | |
206 | SORT(bot, nlower); | |
207 | if (nupper < THRESH) { | |
208 | SORT(mid, nupper); | |
209 | return; | |
6c625db4 | 210 | } |
6c625db4 | 211 | } |
6e0cb3ec KB |
212 | bot = mid; |
213 | nmemb = nupper; | |
214 | } | |
215 | goto partition; | |
216 | /* NOTREACHED */ | |
217 | } | |
218 | ||
219 | static void | |
220 | insertion_sort(bot, nmemb, size, compar) | |
221 | char *bot; | |
222 | register int size; | |
223 | int nmemb, (*compar)(); | |
224 | { | |
225 | register int cnt; | |
226 | register u_char ch; | |
227 | register char *s1, *s2, *t1, *t2, *top; | |
228 | ||
229 | /* | |
230 | * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm | |
231 | * S). Insertion sort has the same worst case as most simple sorts | |
232 | * (O N^2). It gets used here because it is (O N) in the case of | |
233 | * sorted data. | |
234 | */ | |
235 | top = bot + nmemb * size; | |
236 | for (t1 = bot + size; t1 < top;) { | |
237 | for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;); | |
238 | if (t1 != (t2 += size)) { | |
239 | /* Bubble bytes up through each element. */ | |
240 | for (cnt = size; cnt--; ++t1) { | |
241 | ch = *t1; | |
242 | for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2) | |
243 | *s1 = *s2; | |
244 | *s1 = ch; | |
245 | } | |
246 | } else | |
247 | t1 += size; | |
248 | } | |
b4751583 | 249 | } |