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,385be4c68a9e4de6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-07-09 07:48:22 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.cidera.com!Cidera!cyclone.socal.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!twister.socal.rr.com.POSTED!not-for-mail From: "Ron" Newsgroups: comp.lang.ada References: <3D21D581.6EF6CB06@despammed.com> <3D2A0A25.52A62B7C@despammed.com> Subject: Re: Smart sorting algorithm ? X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Message-ID: Date: Tue, 09 Jul 2002 14:48:21 GMT NNTP-Posting-Host: 24.30.156.163 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1026226101 24.30.156.163 (Tue, 09 Jul 2002 07:48:21 PDT) NNTP-Posting-Date: Tue, 09 Jul 2002 07:48:21 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:26970 Date: 2002-07-09T14:48:21+00:00 List-Id: "Wes Groleau": > Wrote an "<" that > first checks a 2D lookup table. If the > answer is "unknown" it does the comparison, > then updates as many cells in the table as > possible. Smart. You avoid making the same comparison more than once and learn from transitivity... No matter what sorting algorithm you use, the table keeps the number of comparison down to nC2=n(n-1)/2 comparisons. The gain from transitivity will depend upon your sorting algorithm, but some will give you no gain at all... > Since the actual comparison was the bottleneck, > the choice of sorting algorithms doesn't matter > any more. No. Though you never gave the range of the number of items to sort, even for small lists the difference between the worst case (nC2 = n(n-1)/2 comparisons) and an O(nlog(n)) sorting algorithm such as heapsort (~ceiling(ln(n!)/ln(2) for small n) is very large. That's 86 more comparisons for n=18 and 489 more for n=36. You want to minimize the number of comparisons, so you need to select a good sorting algorithm... - Ron Zeno