Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!brl-smoke!gwyn
From: gwyn@brl-smoke.ARPA (Doug Gwyn )
Newsgroups: comp.lang.c
Subject: Re: sorting (qsort)
Message-ID: <6684@brl-smoke.ARPA>
Date: Mon, 16-Nov-87 23:43:50 EST
Article-I.D.: brl-smok.6684
Posted: Mon Nov 16 23:43:50 1987
Date-Received: Thu, 19-Nov-87 02:05:49 EST
References: <187@cresswell.quintus.UUCP>
Reply-To: gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 51
Keywords: sorting library

In article <187@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>The UNIX library includes qsort(3), and explicitly says that
>"qsort is an implementation of the quicker-sort algorithm".
>My question is: do these people know something about quicksort
>that I don't?  Contrast merge sort and quicksort:
>(1')	merge sort does o(NlgN) comparisons in the WORST case.
>(1")	quick sort does o(1.4NlgN) comparisons on the AVERAGE.
>	In the worst case it does O(N**2) comparisons.

The UNIX qsort() implementation does fairly well; its worst case is
unlikely to arise in practice.

>(6')	to sort N elements, merge sort needs N additional words
>	for links, but if you have allocated your records
>	dynamically you probably want the links anyway.
>(6")	quick sort doesn't need the links.  On the other hand,
>	if the data items are large, you would be silly to sort
>	the array in place, and would sort an array of pointers
>	instead, so you are generally paying for the links anyway.

This is the key point.  The interface to qsort() is simpler and much
more useful than one that requires links in the records.  An
alternative would be for qsort() to allocate extra dynamic storage
for linkage, sort on the links only, then make a final pass to
rearrange the original records according to the sorted links (this
is "list merge" sorting and it's one of my favorites).  However,
qsort() does not fail due to inability to obtain dynamic memory (heap).

>Have C implementors been hypnotised by the magic word "quick" in
>the name of "quick" sort, or am I missing something?  30% overhead
>seems a lot to pay just for a name.

I doubt the name has anything to do with it; sorting is one of the
few things in the software world that is well understood by most
serious practitioners.  The simplicity of the interface is probably
the main factor, combined with the pre-existence of an implementation
in the UNIX C library.  One is free to implement qsort() any way that
one wishes, so long as it retains the same interface.

Note that neither ANSI C nor POSIX is requiring qsort(), bsearch(),
or other similarly useful general data structure algorithms.

Possibly interesting side note:  Some time ago I implemented a
utility for sorting binary files, similar to the UNIX "sort"
utility.  I started out using qsort() to sort internal merge runs,
but after several passes through the code the only remaining use
of qsort() was to build an initial heap structure, not to do any
actual sorting.  All my sorting ended up being merge sorts, even
the internal run sorting.  In the near future I plan to package
this suitably for installation as a generic binary sorting
utility, and will post it to one of the source newsgroups.