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.3 required=5.0 tests=BAYES_00,FREEMAIL_FROM, REPLYTO_WITHOUT_TO_CC autolearn=no 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 07:02:36 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!news.tele.dk!small.news.tele.dk!193.174.75.178!news-fra1.dfn.de!news-koe1.dfn.de!news.rhrz.uni-bonn.de!news.uni-stuttgart.de!news.belwue.de!news.tesion.net!newsfeed-zh.ip-plus.net!news.ip-plus.net!not-for-mail From: Thomas Wolf Newsgroups: comp.lang.ada Subject: Re: Ada Components - GRACE Lists (Sorting them) Date: Tue, 26 Feb 2002 16:02:31 +0100 Organization: --- Message-ID: References: <3C76EE71.40506@telepath.com> Reply-To: t_wolf@angelfire.com NNTP-Posting-Host: pargate2.paranor.ch X-Trace: rex.ip-plus.net 1014735750 16629 195.65.4.190 (26 Feb 2002 15:02:30 GMT) X-Complaints-To: abuse@ip-plus.net NNTP-Posting-Date: Tue, 26 Feb 2002 15:02:30 +0000 (UTC) X-Newsreader: MicroPlanet Gravity v2.50 Xref: archiver1.google.com comp.lang.ada:20457 Date: 2002-02-26T16:02:31+01:00 List-Id: crmeiners@hotmail.com wrote: > I remembering that there was a discussion about using quicksort for these > 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 > makes this modified quicksort slower on average than heapsort (maybe > mergesort sort also but it doesn't take more space that mergesort). Anyway > the idea is to choose the median of each list (sublist) in linear time. > 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. For lists, mergesort is not a bad choice: worst-case O(n*log n), and the constant factor compared to a quicksort on arrays is not that bad. If you want a quicksort with worst-case O(n*log n), check out introspective sort. Performs just as well as quicksort, but avoids the quadratic worst case. Basically it counts the nesting depth and switches to heapsort if that count gets significantly greater than log n, assuming that in this case, it has hit a worst- case input for quicksort. Because it counts the nesting depth, it can get by with a standard median-of-three pivot selection; no need for fancy things like choosing the true median. -- ----------------------------------------------------------------- Thomas Wolf e-mail: t_wolf@angelfire.com