Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!uunet!mcsun!cernvax!chx400!ethz!neptune!iiic.ethz.ch!mneerach
From: mneerach@iiic.ethz.ch (Matthias Ulrich Neeracher)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <9723@neptune.inf.ethz.ch>
Date: 28 Sep 90 20:23:11 GMT
References: <60123@iuvax.cs.indiana.edu> <1990Sep25.044455.3039@Neon.Stanford.EDU> <7739@ucdavis.ucdavis.edu> <7004@tekig5.PEN.TEK.COM> <60332@iuvax.cs.indiana.edu> <90269.174529CXT105@psuvm.psu.edu>
Sender: news@neptune.inf.ethz.ch
Reply-To: mneerach@iiic.ethz.ch (Matthias Ulrich Neeracher)
Organization: Departement Informatik, ETH, Zurich
Lines: 51

In article <90269.174529CXT105@psuvm.psu.edu> CXT105@psuvm.psu.edu (Christopher Tate) writes:
]In article <60332@iuvax.cs.indiana.edu>, huntley@copper.ucs.indiana.edu (Haydn
]Huntley) says:

]>Perhaps sorting algorithms are an emotional issue -- so many people
]>have posted and mailed trying to tell me that randomizing the
]>algorithm doesn't change it's worst case behavior.  Technically, they
]>are not mistaken, the worst case behavior of fastQsort is N*N, but the
]>chance of observing that behavior is tiny.  If you perform one sort per
]>second for the rest of your life, and you are sorting arrays of 1024
]>elements, I think it is incredibly unlikely that you will observe
]>fastQsort exhibiting worst case behavior before pass on to elsewhere.
]>A person may live for 3 billion seconds, but 1024! is much larger!
]>Fifty factorial is more than 3x10^64, and most calculators can't do
]>more than 69!.

]Attention!  This is NOT a flame!!!

Neither is this...

]For fastQsort, this may well be true -- the random pivots will keep you
]from hitting worst-case pretty effectively.  

No. For random data, a random pivot has exactly the same chance of hitting
worst-case as any `simple' pivot. A median-of-three pivot, however, as
used by Haydn, statistically improves your chances.

]However, for regular qsort,
]the worst case is an already-sorted list.  Even if the list is "almost"
]already sorted, qsort's performance will go down the tubes, and it's
]suprising how often this kind of data set will crop up in supposedly
]"random" lists.

This, however, is true. But this kind of problem could just as easily be
circumvented by picking the middle element of the range instead of the first
one. Still easier than random.

]Yet another reason to use fastQsort instead of THINK's qsort.... :)

If you are really worried about worst case, conside using heapsort instead
of quicksort. Once you get the idea, it's really easy to program. Heapsort
is slower by a constant factor than the average QuickSort case, but it 
performs in almost constant time and in completely constant space. A superb
presentation is given in J. Bentley's "Programming Pearls".

Matthias

-----
Matthias Neeracher                                   mneerach@iiic.ethz.ch
   "These days, though, you have to be pretty technical before you can 
    even aspire to crudeness." -- William Gibson, _Johnny Mnemonic_