Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!psuvax1!psuvm!cxt105
From: CXT105@psuvm.psu.edu (Christopher Tate)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <90269.174529CXT105@psuvm.psu.edu>
Date: 26 Sep 90 21:45:29 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>
Organization: Penn State University
Lines: 31

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!!!

For fastQsort, this may well be true -- the random pivots will keep you
from hitting worst-case pretty effectively.  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.

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

-------
Christopher Tate                 |
                                 |   Sorry; it's classified.  I could tell
    cxt105@psuvm.psu.edu         |    you, but then I'd have to kill you.
    cxt105@psuvm.bitnet          |