Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!swrinde!emory!hubcap!ncrcae!usceast!mgv
From: mgv@usceast.UUCP (Marco Valtorta)
Newsgroups: comp.lang.prolog
Subject: Re: Prolog's Pitfalls Revisited
Message-ID: <3309@usceast.UUCP>
Date: 2 Jul 90 18:37:30 GMT
References: <1990Jun26.170835.11037@chaos.cs.brandeis.edu> <3357@goanna.cs.rmit.oz.au>
Organization: University of South Carolina, Columbia
Lines: 51

In article <3357@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>
>                I said
>! Get this and get this good:  use of quicksort in ANY programming
>! language, is a mark of INCOMPETENCE...
>I did spell out a circumstance (extreme shortage of storage) under
>which the use of quicksort is entirely appropriate.
>
 .....
>Saying that using quicksort is a mark of incompetence is "spiteful"?
>Spare me days.  It's sad times we've come to when one is not allowed
>to disparage an algorithm which has been known to be inferior for
>nearly 30 years without being accused of showing spite to someone.
>WHO, precisely, am I being alleged to have abused?

Here is a quote from David Harel's _Algorithmics_, p.136:
"... Taking into account the fact that it requires only a small fixed amount
of additional storage space, and despite its inferior worst-case performance,
quicksort is actually one of the best sorting algorithms known, and is
definitely the best among the ones mentioned here."  Note that
mergesort is one of the algorithms mentioned in the same section (in
fact, on the previous page). 

It seems that Harel does know that quicksort has been known to be inferior
for nearly 30 years :-).  More seriously, I do not think that either
Knuth or Sedgewick support the view that quicksort is "inferior."
All experimental data (on collections of "random" arrays) I know 
of (admittedly not recent data) points
to quicksort being faster that mergesort on average.  I would like to know
of references to data that supports the opposite view.  Sedgewick's dissertation
on quicksort even has a variant that approaches (as the size of the array to be
sorted increases) the worst-case time performace of mergesort.  (He notes that 
the variant should not to be used in practice, of course.)  

As a bit of trivia 
for the readers of this newsgroup, Van Emden published in CACM a variant of an 
algorithm in CACM called qsort that was supposed to be an improvement of Hoare's
quicksort, but was shown (first empirically, then, by Sedgewick, analytically) 
to be inferior.  (To be precise, Sedgewick showed that Van Emden's analysis
of qsort was incorrect, thus explaining why experiments indicated qsort to
be slower that quicksort.  Still, qsort is a beautiful algorithm!)
I have always assumed that qsort's Van Emden is the same as the one
who co-authored "The Semantics of Predicate Logic as a Programming
Language" with R.A. Kowalski.  Can someone confirm this?

Marco Valtorta			usenet: ...!ncrcae!usceast!mgv
Department of Computer Science	internet: mgv@cs.scarolina.edu
University of South Carolina	tel.: (1)(803)777-4641
Columbia, SC 29208		tlx: 805038 USC
U.S.A.				fax: (1)(803)777-3065
usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv