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