Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!orchid!atbowler
From: atbowler@orchid.UUCP
Newsgroups: comp.lang.c
Subject: Re: sorting (qsort)
Message-ID: <11729@orchid.waterloo.edu>
Date: Wed, 18-Nov-87 15:13:42 EST
Article-I.D.: orchid.11729
Posted: Wed Nov 18 15:13:42 1987
Date-Received: Sat, 21-Nov-87 02:13:08 EST
References: <187@cresswell.quintus.UUCP> <6684@brl-smoke.ARPA>
Reply-To: atbowler@orchid.waterloo.edu (Alan T. Bowler [SDG])
Organization: U. of Waterloo, Ontario
Lines: 46
Keywords: sorting library


In article <6684@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>In article <187@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>
>>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.
>
Personally I've always felt that the problem is that computer science
profs are fascinated by the nice elegant algorithm analysis that
quicksort has.  It is pretty so it gets a lot of time in class.
Shellsort on the other hand has no nice analysis and tends to get
short mention, and students get the idea that quicksort is the
only useful memory resident sort.
    In doing the QSORT for the Honeywell DPS-8 series machines I
chose Shellsort for the implemenation, the interface is the same.
1) The code for Shellsort is simpler and so easier to get right
   I don't know how many times I've had to debug somebody's
   quicksort that didn't for on some data set.
2) If Shellsort is coded as per Knuth's recommended sequence,
   our empirical measurements show that it tends to outperform
   quicksort for small to medium problems (less than 1000 records)
   which is what we expect the QSORT function to be used on anyway.
   Larger problems will probably be done with some type of external
   merge sort (i.e. you will call the system SORT program).
   Shellsort tends to win on the small problems because the simpler
   code reduces the overhead (i.e the constant you multiply the O() by)
   It is definitly true that as the problem gets large enough
   quicksort wins because of the algorithmic advantage (provided
   you don't get a pathological case (O(n**2)), but as I argued above
   this is not the common use of the QSORT() function.
3) Although, I don't know of a good Shellsort analysis, it is clear
   that its worst case behaviour is never as bad as quicksort's.
   This is particularly useful since the naively coded quicksorts
   often exhibit their worse behaviour on presorted or almost sorted
   data which is common in real problems.  (Notice that I said
   naively coded.) It is true that better algorithms to pick the
   pivot element decrease this probablity of a pathological case
   but they also increase the linear factor in the running time.