Author: Dan Newman
Date: 02:08:00 10/21/99
Go up one level in this thread
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.
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:
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.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.