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