Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Fast sort? - Bubble Sort!? (Question to Dr. Hyatt)

Author: Dann Corbit

Date: 11:48:54 10/25/99

Go up one level in this thread


On October 25, 1999 at 12:26:37, Michel Langeveld wrote:
>On October 25, 1999 at 10:17:53, Dann Corbit wrote:
>>On October 23, 1999 at 10:36:40, Robert Hyatt wrote:
>>
>>>On October 22, 1999 at 10:03:29, Dann Corbit wrote:
>>>
>>>>Change to binary insertion and you will see a much bigger benefit.
>>>
>>>I tried both (from Knuth Sorting and Searching).  Binary is very bad for
>>>lists that have 1-5 entries max.  from testing on my machine.  Simple
>>>insertion is no faster than the bubble sort I used, but it also turns out
>>>to be no slower either, after testing Crafty over 300 different positions.
>>>
>>>I think I'll leave insertion in, to prevent such discussions in the
>>>future, however.  :)
>>I have found a new modification to insertion sort (binary or linear) that will
>>make a large improvement in speed.  It has to do with the data movements to
>>perform the actual insertion.  By delaying the insertion, I can do all data
>>movements as a single permutation and never move any element more than once.  It
>>won't work for big lists though, since the code size is O(n!).  With just ten
>>items there are a million leaves in the tree.  However, for very small sublists
>>I think it will do very well.
>
>Best way to prove your statement is code it, and prove it's faster!
>Good news by the way.
Got the idea from a web page.  Here is an example for n=3.  Number of
comparisons is O(n*log(n)).  For the left branch (1,2,3) do not move anything.
For (1,3,2) permute the 3 & 2.  For (3,1,2) and (2,3,1) we must move all of
them, since none is in the right place, and for (3,2,1) we permute 1 & 3.  It is
very simple, really.  I have a code generator to write the output, but I think I
can simplify it a lot and use the inline keyword (it's C99).  The colon in the
diagram means compare.  We don't actually compare twice (e.g. if I test for 1 <
2 I do not have another test for 2<1 {because that only finds equal which is
unlikely and therefore a mostly wasted comparison}

                  1:2
                /     \
             < /     > \
              /         \
           2:3           1:3
           / \           / \
        < / > \       < / > \
         /     \       /     \
      1,2,3    1:3  2,1,3    2:3
               / \           / \
            < / > \       < / > \
             /     \       /     \
          1,3,2   3,1,2 2,3,1   3,2,1




This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.