1 /*- 2 * Copyright (c) 1980, 1983 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.6 (Berkeley) 05/17/90"; 10 #endif /* LIBC_SCCS and not lint */ 11 12 #include <stdlib.h> 13 14 /* 15 * qsort.c: 16 * Our own version of the system qsort routine which is faster by an average 17 * of 25%, with lows and highs of 10% and 50%. 18 * The THRESHold below is the insertion sort threshold, and has been adjusted 19 * for records of size 48 bytes. 20 * The MTHREShold is where we stop finding a better median. 21 */ 22 23 #define THRESH 4 /* threshold for insertion */ 24 #define MTHRESH 6 /* threshold for median */ 25 26 static int (*qcmp)(); /* the comparison routine */ 27 static int qsz; /* size of each record */ 28 static int thresh; /* THRESHold in chars */ 29 static int mthresh; /* MTHRESHold in chars */ 30 31 /* 32 * qsort: 33 * First, set up some global parameters for qst to share. Then, quicksort 34 * with qst(), and then a cleanup insertion sort ourselves. Sound simple? 35 * It's not... 36 */ 37 38 qsort(base, n, size, compar) 39 char *base; 40 int n; 41 int size; 42 int (*compar)(); 43 { 44 register char c, *i, *j, *lo, *hi; 45 char *min, *max; 46 47 if (n <= 1) 48 return; 49 qsz = size; 50 qcmp = compar; 51 thresh = qsz * THRESH; 52 mthresh = qsz * MTHRESH; 53 max = base + n * qsz; 54 if (n >= THRESH) { 55 qst(base, max); 56 hi = base + thresh; 57 } else { 58 hi = max; 59 } 60 /* 61 * First put smallest element, which must be in the first THRESH, in 62 * the first position as a sentinel. This is done just by searching 63 * the first THRESH elements (or the first n if n < THRESH), finding 64 * the min, and swapping it into the first position. 65 */ 66 for (j = lo = base; (lo += qsz) < hi; ) 67 if (qcmp(j, lo) > 0) 68 j = lo; 69 if (j != base) { 70 /* swap j into place */ 71 for (i = base, hi = base + qsz; i < hi; ) { 72 c = *j; 73 *j++ = *i; 74 *i++ = c; 75 } 76 } 77 /* 78 * With our sentinel in place, we now run the following hyper-fast 79 * insertion sort. For each remaining element, min, from [1] to [n-1], 80 * set hi to the index of the element AFTER which this one goes. 81 * Then, do the standard insertion sort shift on a character at a time 82 * basis for each element in the frob. 83 */ 84 for (min = base; (hi = min += qsz) < max; ) { 85 while (qcmp(hi -= qsz, min) > 0) 86 /* void */; 87 if ((hi += qsz) != min) { 88 for (lo = min + qsz; --lo >= min; ) { 89 c = *lo; 90 for (i = j = lo; (j -= qsz) >= hi; i = j) 91 *i = *j; 92 *i = c; 93 } 94 } 95 } 96 } 97 98 /* 99 * qst: 100 * Do a quicksort 101 * First, find the median element, and put that one in the first place as the 102 * discriminator. (This "median" is just the median of the first, last and 103 * middle elements). (Using this median instead of the first element is a big 104 * win). Then, the usual partitioning/swapping, followed by moving the 105 * discriminator into the right place. Then, figure out the sizes of the two 106 * partions, do the smaller one recursively and the larger one via a repeat of 107 * this code. Stopping when there are less than THRESH elements in a partition 108 * and cleaning up with an insertion sort (in our caller) is a huge win. 109 * All data swaps are done in-line, which is space-losing but time-saving. 110 * (And there are only three places where this is done). 111 */ 112 113 static 114 qst(base, max) 115 char *base, *max; 116 { 117 register char c, *i, *j, *jj; 118 register int ii; 119 char *mid, *tmp; 120 int lo, hi; 121 122 /* 123 * At the top here, lo is the number of characters of elements in the 124 * current partition. (Which should be max - base). 125 * Find the median of the first, last, and middle element and make 126 * that the middle element. Set j to largest of first and middle. 127 * If max is larger than that guy, then it's that guy, else compare 128 * max with loser of first and take larger. Things are set up to 129 * prefer the middle, then the first in case of ties. 130 */ 131 lo = max - base; /* number of elements as chars */ 132 do { 133 mid = i = base + qsz * ((lo / qsz) >> 1); 134 if (lo >= mthresh) { 135 j = (qcmp((jj = base), i) > 0 ? jj : i); 136 if (qcmp(j, (tmp = max - qsz)) > 0) { 137 /* switch to first loser */ 138 j = (j == jj ? i : jj); 139 if (qcmp(j, tmp) < 0) 140 j = tmp; 141 } 142 if (j != i) { 143 ii = qsz; 144 do { 145 c = *i; 146 *i++ = *j; 147 *j++ = c; 148 } while (--ii); 149 } 150 } 151 /* 152 * Semi-standard quicksort partitioning/swapping 153 */ 154 for (i = base, j = max - qsz; ; ) { 155 while (i < mid && qcmp(i, mid) <= 0) 156 i += qsz; 157 while (j > mid) { 158 if (qcmp(mid, j) <= 0) { 159 j -= qsz; 160 continue; 161 } 162 tmp = i + qsz; /* value of i after swap */ 163 if (i == mid) { 164 /* j <-> mid, new mid is j */ 165 mid = jj = j; 166 } else { 167 /* i <-> j */ 168 jj = j; 169 j -= qsz; 170 } 171 goto swap; 172 } 173 if (i == mid) { 174 break; 175 } else { 176 /* i <-> mid, new mid is i */ 177 jj = mid; 178 tmp = mid = i; /* value of i after swap */ 179 j -= qsz; 180 } 181 swap: 182 ii = qsz; 183 do { 184 c = *i; 185 *i++ = *jj; 186 *jj++ = c; 187 } while (--ii); 188 i = tmp; 189 } 190 /* 191 * Look at sizes of the two partitions, do the smaller 192 * one first by recursion, then do the larger one by 193 * making sure lo is its size, base and max are update 194 * correctly, and branching back. But only repeat 195 * (recursively or by branching) if the partition is 196 * of at least size THRESH. 197 */ 198 i = (j = mid) + qsz; 199 if ((lo = j - base) <= (hi = max - i)) { 200 if (lo >= thresh) 201 qst(base, j); 202 base = i; 203 lo = hi; 204 } else { 205 if (hi >= thresh) 206 qst(i, max); 207 max = j; 208 } 209 } while (lo >= thresh); 210 } 211