From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,d75494dd10472a30
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-02-26 08:59:11 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: dennison@telepath.com (Ted Dennison)
Newsgroups: comp.lang.ada
Subject: Re: Ada Components - GRACE Lists (Sorting them)
Date: 26 Feb 2002 08:59:11 -0800
Organization: http://groups.google.com/
Message-ID: <4519e058.0202260859.4ecde69f@posting.google.com>
References: <a48p2k$nop$1@nh.pace.co.uk> <3C76EE71.40506@telepath.com>
 <a5fs6c$2cir$1@msunews.cl.msu.edu>
NNTP-Posting-Host: 65.115.221.98
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1014742751 2041 127.0.0.1 (26 Feb 2002 16:59:11
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 26 Feb 2002 16:59:11 GMT
Xref: archiver1.google.com comp.lang.ada:20467
Date: 2002-02-26T16:59:11+00:00
List-Id: <comp.lang.ada>

"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