Newsgroups: comp.programming
From: hoey@zogwarg.tec.army.mil (Dan Hoey)
Date: 16 Jul 93 20:42:09 GMT
Subject: Re: Measuring Time for First Output

d...@ccr-p.ida.org (David desJardins) writes:

>If there is a problem with quicksort in an application, it is more
>likely to be due to some other problem, like its variable running time
>and poor worst-case behavior.

m...@hubcap.clemson.edu (M. J. Saltzman) writes:

>Defeating poor worst-case running time isn't that hard.  You can use
>a median-of-three rule to select the partition element, which makes
>the worst case extremely unlikely.

This seems to miss the point completely.  You can't defeat worst-case
behavior by making it less likely.  Changing the likelihood affects
average-case behavior, and perhaps reduces the variance, and may
affect other statistical measures.  But if you want good worst-case
behavior, you need to minimize the maximum running time.  That's the
definition of worst-case behavior.

Fortunately, this is possible for quicksort.  There are known linear-
time median-finding algorithms that can be used to partition the set
exactly in half.  I think you can save some time if you use a
algorithm that guarantees finding an r-tile to partition on--i.e., an
element with at least rn elements on either side.  As long as the
r-tile algorithm is O(n) time, you are guaranteed O(n log n) worst
case time.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil