* Copyright (c) 1980 Regents of the University of California.
* Redistribution and use in source and binary forms are permitted
* provided that the above copyright notice and this paragraph are
* duplicated in all such forms and that any documentation,
* advertising materials, and other materials related to such
* distribution and use acknowledge that the software was developed
* by the University of California, Berkeley. The name of the
* University may not be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)qsort.c 5.4 (Berkeley) 6/27/88";
#endif /* LIBC_SCCS and not lint */
* Our own version of the system qsort routine which is faster by an average
* of 25%, with lows and highs of 10% and 50%.
* The THRESHold below is the insertion sort threshold, and has been adjusted
* for records of size 48 bytes.
* The MTHREShold is where we stop finding a better median.
#define THRESH 4 /* threshold for insertion */
#define MTHRESH 6 /* threshold for median */
static int (*qcmp
)(); /* the comparison routine */
static int qsz
; /* size of each record */
static int thresh
; /* THRESHold in chars */
static int mthresh
; /* MTHRESHold in chars */
* First, set up some global parameters for qst to share. Then, quicksort
* with qst(), and then a cleanup insertion sort ourselves. Sound simple?
qsort(base
, n
, size
, compar
)
register char c
, *i
, *j
, *lo
, *hi
;
* First put smallest element, which must be in the first THRESH, in
* the first position as a sentinel. This is done just by searching
* the first THRESH elements (or the first n if n < THRESH), finding
* the min, and swapping it into the first position.
for (j
= lo
= base
; (lo
+= qsz
) < hi
; )
for (i
= base
, hi
= base
+ qsz
; i
< hi
; ) {
* With our sentinel in place, we now run the following hyper-fast
* insertion sort. For each remaining element, min, from [1] to [n-1],
* set hi to the index of the element AFTER which this one goes.
* Then, do the standard insertion sort shift on a character at a time
* basis for each element in the frob.
for (min
= base
; (hi
= min
+= qsz
) < max
; ) {
while (qcmp(hi
-= qsz
, min
) > 0)
if ((hi
+= qsz
) != min
) {
for (lo
= min
+ qsz
; --lo
>= min
; ) {
for (i
= j
= lo
; (j
-= qsz
) >= hi
; i
= j
)
* First, find the median element, and put that one in the first place as the
* discriminator. (This "median" is just the median of the first, last and
* middle elements). (Using this median instead of the first element is a big
* win). Then, the usual partitioning/swapping, followed by moving the
* discriminator into the right place. Then, figure out the sizes of the two
* partions, do the smaller one recursively and the larger one via a repeat of
* this code. Stopping when there are less than THRESH elements in a partition
* and cleaning up with an insertion sort (in our caller) is a huge win.
* All data swaps are done in-line, which is space-losing but time-saving.
* (And there are only three places where this is done).
register char c
, *i
, *j
, *jj
;
* At the top here, lo is the number of characters of elements in the
* current partition. (Which should be max - base).
* Find the median of the first, last, and middle element and make
* that the middle element. Set j to largest of first and middle.
* If max is larger than that guy, then it's that guy, else compare
* max with loser of first and take larger. Things are set up to
* prefer the middle, then the first in case of ties.
lo
= max
- base
; /* number of elements as chars */
mid
= i
= base
+ qsz
* ((lo
/ qsz
) >> 1);
j
= (qcmp((jj
= base
), i
) > 0 ? jj
: i
);
if (qcmp(j
, (tmp
= max
- qsz
)) > 0) {
/* switch to first loser */
* Semi-standard quicksort partitioning/swapping
for (i
= base
, j
= max
- qsz
; ; ) {
while (i
< mid
&& qcmp(i
, mid
) <= 0)
tmp
= i
+ qsz
; /* value of i after swap */
/* j <-> mid, new mid is j */
/* i <-> mid, new mid is i */
tmp
= mid
= i
; /* value of i after swap */
* Look at sizes of the two partitions, do the smaller
* one first by recursion, then do the larger one by
* making sure lo is its size, base and max are update
* correctly, and branching back. But only repeat
* (recursively or by branching) if the partition is
* of at least size THRESH.
if ((lo
= j
- base
) <= (hi
= max
- i
)) {