Re: Ada Components - GRACE Lists (Sorting them)

[dennison@telepath.com (Ted Dennison)]

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<a5fs6c$2cir$1@msunews.cl.msu.edu>...
> list components.  There was naturally concern about the O(n^2) worst case
> performance.  If people are still worried about this issue, I have a
> solution that guarantees that quicksort worst case is O(n*log n).  Before
> any of you spill your coffee ;-) there is a hefty constant involved that
...
> There happens to be a 'well known algorithm' for this.  The only drawback is
> a hit on the constant.  I figure it might not be too bad of a price to pay,
> though.

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), then we'll be saving
everyone a lot of CPU time in the aggregate by using a fast Quicksort.
If we blow that, in my book we might as well use something else and
keep the code simple.

When I do finally manage to find a suitable forum to publish the
implmentation I have, we should certianly encourage folks to play with
the algorithm, modify it, analayze the results, and report their
findings for discussion. But again, I don't think we should waste a
huge amount of effort on it, because this isn't the sort that will
really matter. That one will be in the "Maps" package, and will
probably have to be some kind of tree-based sort.

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