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.9 (Berkeley) 02/23/91"; 10 #endif /* LIBC_SCCS and not lint */ 11 12 #include <sys/types.h> 13 #include <stdlib.h> 14 15 /* 16 * MTHRESH is the smallest partition for which we compare for a median 17 * value instead of using the middle value. 18 */ 19 #define MTHRESH 6 20 21 /* 22 * THRESH is the minimum number of entries in a partition for continued 23 * partitioning. 24 */ 25 #define THRESH 4 26 27 void 28 qsort(bot, nmemb, size, compar) 29 void *bot; 30 size_t nmemb, size; 31 int (*compar) __P((const void *, const void *)); 32 { 33 static void insertion_sort(), quick_sort(); 34 35 if (nmemb <= 1) 36 return; 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; 95 static void insertion_sort(); 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 104 /* 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. 108 */ 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; 123 } 124 } 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; 144 } 145 goto swap; 146 } 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; 158 } 159 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 } 175 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 */ 186 187 /* 188 * If must call recursively, do it on the smaller partition; this 189 * bounds the stack to lg N entries. 190 */ 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; 199 } 200 } 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; 210 } 211 } 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 } 249 } 250