Path: utzoo!attcan!uunet!samsung!crackers!m2c!jjmhome!zinn!wgc386!slum!laird
From: laird@slum.MV.COM (Laird Heal)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Summary: Optimal optimizations
Keywords: Quicksort qsort()
Message-ID: <1990Sep30.003013.736@slum.MV.COM>
Date: 30 Sep 90 00:30:13 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>
Organization: dis
Lines: 47

Excuse me for coagulating this burgeoning thread, but one can test for
the "worst case" of vanilla Quick Sort without too much difficulty; in
the first pass one normally makes at least one comparison against each
of the keys.  I have not developed an heuristic but I would not expect
it to be too hard to determine if the incoming list were suited to the
algorithm.  Making the same optimization on a random pivot is possible 
but not as clear.

The first pass could check for sorted input or enclosed sorted series.
This determination would be O(n) and thus not burdensome on very large
lists, the only ones worth discussing.  The options would be to select
a portion of the list and apply Quick Sort or another algorithm.  What
is the best algorithm on a list of, say, ten or fewer items?

[quotations follow; hit 'n' except for reference]

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!!!
>
>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.... :)
>
-- 

Laird Heal	laird@slum.MV.COM	Dishonesty is the best politics.
(Salem, NH)	+1 603 898 1406         Disclaimer:  if you want'er.