Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 07:21:04 10/20/99

Go up one level in this thread


On October 20, 1999 at 00:56:03, Dann Corbit wrote:

>On October 19, 1999 at 23:53:38, Robert Hyatt wrote:
>[snip]
>>One other point.  "insertion sort" won't work here.  Because I do the following:
>>
>>1.  generate all the moves (they are placed in the moves[] array as they are
>>generated so that we end up with the moves already in the array before we start
>>the 'sort').
>>
>>2.  compute the 'sort score'.  The moves are in the list, so a parallel array
>>is used to hold the scores.  These scores are produced move by move.
>>
>>3.  sort both arrays at the same time so that the moves 'stick' with the scores.
>>
>>It would be very hard to produce code that does the above, yet uses fewer
>>instructions (overall) than the simple bubble sort currently used.  If I
>>generated moves one at a time, perhaps 'insertion' would work.  But the code
>>to generate moves doesn't work like that (the overhead would be murder to
>>keep calling the generator to get the next move.)
>You can call insertion sort on a random array.  It starts with the first element
>as an ordered set.  Then it inserts the second element into this set.  Then it
>inserts the 3rd element, etc.


Right... but count the memory references.  My moves _must_ be put in the
right array (the array where they are stuck when they are generated.)  This
means that I copy them to another array, then 'insertion sort' them back to
the original array, which copies each element twice.  Bubble sort eats that
alive in terms of total instructions, number of memory references, and
number of cache misses.  For very small N of course.



This page took 0.01 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.