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-10 07:39:28 PST Path: archiver1.google.com!news2.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!news.maxwell.syr.edu!news.he.net!cyclone-sf.pbi.net!151.164.30.35!cyclone.swbell.net!bos-service1.ext.raytheon.com!bos-service2.ext.raytheon.com.POSTED!not-for-mail Message-ID: <3D2C46FD.AD325907@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> <3D2A0A25.52A62B7C@despammed.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Wed, 10 Jul 2002 09:38:53 -0500 NNTP-Posting-Host: 151.168.144.162 X-Complaints-To: news@ext.ray.com X-Trace: bos-service2.ext.raytheon.com 1026311967 151.168.144.162 (Wed, 10 Jul 2002 10:39:27 EDT) NNTP-Posting-Date: Wed, 10 Jul 2002 10:39:27 EDT Organization: Raytheon Company Xref: archiver1.google.com comp.lang.ada:26988 Date: 2002-07-10T09:38:53-05:00 List-Id: > 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... Someone suggested by e-mail/CGI (no return address) that I use bucket sort. But that won't work: the items have an order, but no numeric value until the sorting is complete. Hence there is no way to assign any particular item to any particular bucket until the sorting is complete. Background: We're taking a set of strings and asking a human to make a better/worse value judgment on each pair. The only numeric value is the position in the sorted list. The lookup table for transitivity uses the position in the unsorted list. "<" (L,R) is: if L better than R, return true .... Lookup : .... := (others => (others => Unknown)); .... if Input (A) < Input (B) then Lookup (A,B) := Correct; if Lookup (B,C) = Correct then -- inference Lookup (A,C) := Correct; If "=" is prevented or disallowed, then there are four inferences for every C, and C loops through Input'Range. Recursion could add more inferences for each inference made. -- Wes Groleau http://freepages.rootsweb.com/~wgroleau