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