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