Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!ucdavis!iris!lim
From: lim@iris.ucdavis.edu (Lloyd Lim)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <7739@ucdavis.ucdavis.edu>
Date: 25 Sep 90 08:41:35 GMT
References: <60123@iuvax.cs.indiana.edu> <1990Sep25.044455.3039@Neon.Stanford.EDU>
Sender: usenet@ucdavis.ucdavis.edu
Reply-To: lim@iris.ucdavis.edu (Lloyd Lim)
Organization: U.C. Davis - Department of Electrical Engineering and Computer Science
Lines: 32

In article <1990Sep25.044455.3039@Neon.Stanford.EDU> kaufman@Neon.Stanford.EDU (Marc T. Kaufman) writes:
>In article <60123@iuvax.cs.indiana.edu> huntley@copper.ucs.indiana.edu (Haydn Huntley) writes:
>	
>>One problem with qsort is that when the data is not in random order -- for 
>>example when it's already ordered, in reverse order, or almost sorted -- then 
>>qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can 
>>take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort 
>>algorithm doesn't have this problem, because it randomly selects the pivot 
>>element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.
>
>Without considering the other features of fastQSort, I really have to object
>to the comment that fastQSort doesn't have a "worst case" problem because of
>"random" selection.  Just because it may not be predictable doesn't mean it
>doesn't exist -- only that you will be bitten when you least expect it.
>
>Using "random numbers" is not a substitute for analysis of the algorithm.

Marc is correct.  When you select a random pivot, you still have the same
worst case running time.  If all permutations are equally likely, a random
pivot does not help you at all.  In practice, however, reverse order
arrangements are somewhat more probable than totally disordered arrangements.
Thus a random pivot helps a little in practice.

A better way is to pick the median of three elements (the first, middle, and
last elements).  This method is fast and it does reduce the probability of
encountering the worst case - both in theory and practice.  The worst case is
still there, of course.

+++
Lloyd Lim     Internet: lim@iris.ucdavis.edu (128.120.57.20)
              Compuserve: 72647,660
              US Mail: 146 Lysle Leach Hall, U.C. Davis, Davis, CA 95616