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