Author: Ricardo Gibert
Date: 08:38:46 10/21/99
Go up one level in this thread
On October 21, 1999 at 05:08:00, Dan Newman wrote:
>On October 20, 1999 at 15:40:50, Robert Hyatt wrote:
>
>>On October 20, 1999 at 13:22:26, Dann Corbit wrote:
>>
>>>On October 20, 1999 at 10:21:04, Robert Hyatt wrote:
>>>[snip]
>>>>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.
>>>
>>>Insertion sort is stable and in-place.
>>
>>
>>It is stable, but it isn't "in place" in the context that you have a complete
>>list _before_ you can start the insertion sort. IE I start with the list of
>>moves _before_ I even get a chance to do anything with them. Now I have to
>>get that list in order based on scores in another vector. I am going to have to
>>do the insertion sort into a second array, then copy this back over the first
>>array, or else do the same sort of 'shuffling' I do in the bubble sort.
>>
>>Convince me it is faster and I'll certainly change, as I never look 'speed' in
>>the mouth. :)
>
>I looked up bubble sort and insertion sort in my old PL/1 book and
>found that its description of insertion sort was about the same as
>yours--specifically, it's not an in-place sort. I looked back at my
>copy of Numerical Recipes (which is where I got what I've been calling
>"insertion sort") and now I see their name for what I've been using
>is actually "straight insertion" which (unlike the "insertion sort"
>of my PL/1 book) *is* an in-place technique.
>
>Bubble Sort with early exit:
>
> finished = 0;
> j = N-1;
> while( !finished && j > 0 ) {
> finished = 1;
> for( i = 0; i < j; i++ ) {
> if( arr[i] < arr[i+1] ) {
> temp = arr[i];
> arr[i] = arr[i+1];
> arr[i+1] = temp;
> finished = 0;
> }
> }
> j--;
> }
>
>Straight Insertion:
>
> for( j = 1; j < N; j++ ) {
> temp = arr[j];
> i = j-1;
> while( i >= 0 && arr[i] < temp ) {
> arr[i+1] = arr[i];
> i--;
> }
> arr[i+1] = temp;
> }
>
>As you can see straight insertion seems simpler (fewer lines of code)
>but is slightly more difficult to follow.
There is a simple improvement that uses a sentinel, which simplifies the test in
the inner loop.
>
>I tried these two out and straight insertion was faster than the
>bubble sort. If I subtract out the overhead for loading the array
>up with random numbers here's what I get:
Crafty uses bubble sort to sort arrays that are already nearly sorted. The test
with random numbers is not the right test. However, I'm not sure what the
difference is between a randomly ordered 3 element array and a nearly sorted 3
element array. Certainly, there is no difference with 2 element arrays.
>
> Array Length: 2 3 6
> Bubble Sort: 9.18 19.43 67.66
>Straight Insertion: 9.18 15.94 41.41
>
>The figures are time (seconds) to do 50M iterations on a P6/200.
>
>Anyway, it's not a whole lot faster, and it may be possible that
>the best implementation of each will have different results than the
>above...
>
>-Dan.
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.