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=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cda33fc7f63c2885 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-08 11:12:40 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!xmission!news-hog.berkeley.edu!ucberkeley!nntp-relay.ihug.net!ihug.co.nz!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: <7iE_7.8661$cD4.15714@www.newsranger.com> <3c3b13ba$0$212$626a54ce@news.free.fr> <3c3b2aa0$0$212$626a54ce@news.free.fr> Subject: Re: list strawman Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Tue, 08 Jan 2002 14:12:31 EST Organization: http://www.newsranger.com Date: Tue, 08 Jan 2002 19:12:31 GMT Xref: archiver1.google.com comp.lang.ada:18659 Date: 2002-01-08T19:12:31+00:00 List-Id: In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says... > >I'm sorry, I was thinking about heap sort. Ahh. Yeah, heapsort would probably be a bad idea in this package. In a *.Maps package it might make sense, if things are already kept in a heap anyway. >Yes. There is still the problem of choosing the pivot. With random >access, I'd use a random element. Without random access, you'll have >to choose the first or the last element and then degenerate in N^2 for >a sorted input, not something I'd like in a general purpose library. That's a good point. It would probably be fairly easy to alternate which side the pivot is taken from. Then again, I think the advice to use a different package if sorting is *really* important to you should mitagate this issue. Also, we provide tools to insert into a pre-sorted list, so the only reason anyone should ever hit the worst case is ignorance or really bad luck. >Well, I think I'd still choose a merge sort. I believe the splitting part of mergesort would involve a linear search for a linked-list. That would take us into O(n*2) territory, if not worse. In my student days I could figure out the exact factor...hmmm...perhaps its just another nlogn... Despite taking Computer Science Algorithms courses no less than 3 times (or perhaps *because* I had to :-) ), I'm not really a sorting expert. But all the literature I read highly suggests one use Quicksort, despite its theoretical O(n**2) behavior. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html is a good example. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced.