Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!shelby!neon!kaufman
From: kaufman@Neon.Stanford.EDU (Marc T. Kaufman)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <1990Sep25.044455.3039@Neon.Stanford.EDU>
Date: 25 Sep 90 04:44:55 GMT
References: <60123@iuvax.cs.indiana.edu>
Organization: Computer Science Department, Stanford University
Lines: 17

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 Kaufman (kaufman@Neon.stanford.edu)