Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!sol.ctr.columbia.edu!cica!iuvax!copper!huntley
From: huntley@copper.ucs.indiana.edu (Haydn Huntley)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <60287@iuvax.cs.indiana.edu>
Date: 25 Sep 90 21:46:24 GMT
References: <60123@iuvax.cs.indiana.edu> <1990Sep25.044455.3039@Neon.Stanford.EDU> <7739@ucdavis.ucdavis.edu>
Sender: news@iuvax.cs.indiana.edu
Organization: Indiana University, Bloomington IN.
Lines: 41

In article <7739@ucdavis.ucdavis.edu> lim@iris.ucdavis.edu (Lloyd Lim) writes:
| >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.
| 

Actually, I implemented 15 different sorting algorithms, of which 10
were variations on Quick Sort, and using the median of the first,
middle, and last elements was not one of the better Quick Sort
variations!  It *surprised* me too!

Have you studied the analysis of algorithms?  Marc is quite right that
using random numbers is not a substitute for the careful analysis of
an algorithm, but I think if you take a look at this implementation of
the Quick Sort algorithm, you will find that it is quite efficient --
and it is *much* more efficient than the one in the library.

The way to calculate the possibility of that algorithm receiving it's
worst case input is 1/N!, where N is the number of items in the list
to be sorted.  If N > 10, that number is *vanishingly* small, much
smaller than the chance of being struck by lightning, etc., etc.  If N
<= 10, then that randomized algorithm will sort the data so quickly,
that it doesn't much matter whether it hits it's worst case or not!

Hows that for a (tongue-in-cheek) careful analysis!

:-)

--Haydn
;;  *****************************************************
;;  *  Haydn Huntley    huntley@copper.ucs.indiana.edu  *
;;  *****************************************************