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