Re: Ada Components - GRACE Lists (Sorting them)

[dennison@telepath.com (Ted Dennison)]

Darren New <dnew@san.rr.com> wrote in message news:<3C7BC3CD.3B7A46DC@san.rr.com>...
> Ted Dennison wrote:
> > The main reason I was inclined to stick with Quicksort is that it is
> > on *average* the fastest sort available. If "average case" is truly
> > the average (a big "if", I'll grant you),
> 
> The only problem with quicksort's worst-case behavior is that it occurs
> when the list is already mostly sorted. The distribution of worst-case
> cases isn't random, and it's easy to code in a way that hits the worst
> case on a regular basis.

Right. But if you are aware of this issue, its also fairly easy to
code in a way that it *doesn't* hit the worst case.

Also (and this is the part I don't think a lot of folks realise), the
constants on quicksort vs. other sorts are such that "n" often has to
be damn large before Quicksort's n**2 is worse than other algorithms'
nlogn. I'd argue that anyone sorting that large an amount of stuff
should be using the Maps package anyway.

-- 
T.E.D.
Home     -  mailto:dennison@telepath.com (Yahoo: Ted_Dennison)
Homepage -  http://www.telepath.com/dennison/Ted/TED.html