Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 20:34:04 10/18/99

Go up one level in this thread


On October 18, 1999 at 17:28:12, Oliver Roese wrote:

>On October 18, 1999 at 16:48:51, leonid wrote:
>
>>On October 18, 1999 at 14:03:49, KarinsDad wrote:
>>
>>>On October 16, 1999 at 07:59:32, leonid wrote:
>(...)
>>>>If somebogy will mention what is the "bubble sort" it will be appreciated.
>>>>
>>>>Leonid.
>
>(...Explanation)
>>
>>Thanks for responding!
>>
>(...)
>
>
>BTW, by glancing through an older crafty version i stumpeld across a remarkable
>comment there. Dr. Hyatt says there, that Bubblesort has outperformed all other
>sortalgorithms for a particular sortproblem!
>This is amazing, since AFAIK Bubblesort is the one documented sort-algorithm
>that is theoretically dominated by any other documented sort-algorithm.
>Consequently it is doomed by many as the "poor-mans-sort."
>Since i assume Dr. Hyatt knows what he say, we have a counterexample.
>Is there a explanation to that?
>
>Best Regards
>Oliver


yes...  a couple.  First, it is not uncommon to have one reasonable capture,
and it is very common to have only 2-3.  Compare bubble-sort (with early exit)
to quicksort.  But compare the total number of instructions executed, not the
number of items/comparisons done.  You'll get the idea quickly.  Bubble sort
is very good for really small N.  And captures are _always_ small N.

Second, bubble sort runs with two branches in the loop, counting the loop
branch itself.  quicksort is much worse.

Third, bubble sort is very small, with the resulting small cache footprint,
which avoids dislodging other important data in the small L1/L2 cache.

If I knew that N would be 40, or if I couldn't generate captures by themselves
and had to sort all the moves, I would use something else.  But when N=1,2,3
(typically) bubble-sort is impossible to beat.



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.