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