* Copyright (c) 1980, 1983, 1990 The Regents of the University of California.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91";
#endif /* LIBC_SCCS and not lint */
* MTHRESH is the smallest partition for which we compare for a median
* value instead of using the middle value.
* THRESH is the minimum number of entries in a partition for continued
qsort(bot
, nmemb
, size
, compar
)
int (*compar
) __P((const void *, const void *));
static void insertion_sort(), quick_sort();
quick_sort(bot
, nmemb
, size
, compar
);
insertion_sort(bot
, nmemb
, size
, compar
);
* Swap two areas of size number of bytes. Although qsort(3) permits random
* blocks of memory to be sorted, sorting pointers is almost certainly the
* common case (and, were it not, could easily be made so). Regardless, it
* isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
* arithmetic gets lost in the time required for comparison function calls.
* Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass
* of straight insertion sort after partitioning is complete is better than
* sorting each small partition as it is created. This isn't correct in this
* implementation because comparisons require at least one (and often two)
* function calls and are likely to be the dominating expense of the sort.
* Doing a final insertion sort does more comparisons than are necessary
* because it compares the "edges" and medians of the partitions which are
* known to be already sorted.
* This is also the reasoning behind selecting a small THRESH value (see
* Knuth, page 122, equation 26), since the quicksort algorithm does less
* comparisons than the insertion sort.
if (compar(t1, bot) < 0) \
insertion_sort(bot, n, size, compar); \
quick_sort(bot
, nmemb
, size
, compar
)
register char *top
, *mid
, *t1
, *t2
;
static void insertion_sort();
/* bot and nmemb must already be set. */
/* find mid and top elements */
mid
= bot
+ size
* (nmemb
>> 1);
top
= bot
+ (nmemb
- 1) * size
;
* Find the median of the first, last and middle element (see Knuth,
* Vol. 3, page 123, Eq. 28). This test order gets the equalities
t1
= compar(bot
, top
) < 0 ? top
: bot
;
else if (n1
> 0 && n2
< 0)
t1
= compar(bot
, top
) > 0 ? top
: bot
;
/* if mid element not selected, swap selection there */
/* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
for (; bot
< mid
&& compar(bot
, mid
) <= 0; bot
+= size
);
if (compar(mid
, top
) <= 0) {
newbot
= bot
+ size
; /* value of bot after swap */
if (bot
== mid
) /* top <-> mid, mid == top */
/* bot <-> mid, mid == bot */
newbot
= mid
= bot
; /* value of bot after swap */
swap
: SWAP(bot
, replace
);
* Quicksort behaves badly in the presence of data which is already
* sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
* To avoid this worst case behavior, if a re-partitioning occurs
* without swapping any elements, it is not further partitioned and
* is insert sorted. This wins big with almost sorted data sets and
* only loses if the data set is very strangely partitioned. A fix
* for those data sets would be to return prematurely if the insertion
* sort routine is forced to make an excessive number of swaps, and
* continue the partitioning.
insertion_sort(bsv
, nmemb
, size
, compar
);
* Re-partition or sort as necessary. Note that the mid element
* itself is correctly positioned and can be ignored.
nlower
= (mid
- bot
) / size
; /* size of lower partition */
nupper
= nmemb
- nlower
- 1; /* size of upper partition */
* If must call recursively, do it on the smaller partition; this
* bounds the stack to lg N entries.
quick_sort(mid
, nupper
, size
, compar
);
quick_sort(bot
, nlower
, size
, compar
);
insertion_sort(bot
, nmemb
, size
, compar
)
register char *s1
, *s2
, *t1
, *t2
, *top
;
* A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm
* S). Insertion sort has the same worst case as most simple sorts
* (O N^2). It gets used here because it is (O N) in the case of
top
= bot
+ nmemb
* size
;
for (t1
= bot
+ size
; t1
< top
;) {
for (t2
= t1
; (t2
-= size
) >= bot
&& compar(t1
, t2
) < 0;);
if (t1
!= (t2
+= size
)) {
/* Bubble bytes up through each element. */
for (cnt
= size
; cnt
--; ++t1
) {
for (s1
= s2
= t1
; (s2
-= size
) >= t2
; s1
= s2
)