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