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,385be4c68a9e4de6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-07-02 13:15:08 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!bloom-beacon.mit.edu!nycmny1-snh1.gtei.net!cambridge1-snf1.gtei.net!news.gtei.net!bos-service1.ext.raytheon.com!dfw-service2.ext.raytheon.com.POSTED!not-for-mail Message-ID: <3D220648.6F3BE45D@despammed.com> From: Wes Groleau Reply-To: wesgroleau@despammed.com X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) X-Accept-Language: en,es-MX,es,pt,fr-CA,fr MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Smart sorting algorithm ? References: <3D21D581.6EF6CB06@despammed.com> <3D21DC25.AD402F70@easystreet.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Tue, 02 Jul 2002 15:00:08 -0500 NNTP-Posting-Host: 151.168.144.162 X-Complaints-To: news@ext.ray.com X-Trace: dfw-service2.ext.raytheon.com 1025640039 151.168.144.162 (Tue, 02 Jul 2002 15:00:39 CDT) NNTP-Posting-Date: Tue, 02 Jul 2002 15:00:39 CDT Organization: Raytheon Company Xref: archiver1.google.com comp.lang.ada:26819 Date: 2002-07-02T15:00:08-05:00 List-Id: > > The reason I'm asking is that I have a situation > > where deciding the order of two items is very slow. > > > > If the program determines that A < B and later > > determines that B < C and stores this information, > > then if and when A ? C comes up, it can determine > > the answer from the stored information. > > Using, e.g., qsort, isn't it true that this should not happen? If > you've compared A vs B and B vs C, then B is the pivot, and A and C > are on opposite sides of the pivot and won't get compared. Interesting point. On a test of 18 items, one sort took 42 compares. Another test of 18 items took 76 compares. And a test of 36 items to 172 compares. I've discarded detailed logs, but it seems to me I saw several times the same two items being compared. This is a variation of quicksort where only one of the two slices is recursive. Author claims it saves a heck of a lot of memory. I don't really care about memory, but it was the first open source Ada sort in my search results. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau