Re: Smart sorting algorithm ?

[Wes Groleau <wesgroleau@despammed.com>]

> 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