xref: /csrg-svn/lib/libc/stdlib/qsort.c (revision 11449)
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