qsort (was Looking for portable sort algorithm)
Chris Torek
chris at mimsy.UUCP
Thu Sep 21 19:51:37 AEST 1989
In article <5217 at merlin.usc.edu> jeenglis at nunki.usc.edu (Joe English) writes:
>As long as we're on the subject of sorting, I was
>wondering why the standard sort routine is implemented
>as a quick-sort nearly everywhere, given its poor
>worst-case behaviour. Any guesses?
If true: laziness. If not: well, no answering `why' for a question
that is false. (qsort simply means `apply some reasonably fast sort',
not `apply quicksort'. There is no reason someone could not put in all
sorts of sorts, selected automatically at runtime, perhaps.) It is
worth noting that 4.3BSD uses a modified quick sort that (a) chooses
one of three for its partition element and (b) switches to an insertion
sort when the number of items in a partition is `small' (<= 10). It
also does the larger partition using tail recursion (i.e., `goto') so
that the stack does not get as deep. The `median of three' keeps
qsort from being worst-case on nearly sorted arrays. The insertion
sort should be obvious.
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain: chris at mimsy.umd.edu Path: uunet!mimsy!chris
More information about the Comp.lang.c
mailing list