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