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