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