Hi Carey,
CB>GW>CB>comparisons and exchanges aren't really the whole story. (I should 
als
CB>GW>CB>point out that with most real 'bubble sorts', there will only be 'n'
CB>GW>CB>exchanges.  Most implementations will find the highest/lowest and 
then
CB>GW>I'm glad you said 'bubble sort', because as soon as you change to the
CB>GW>method you describe it is no longer a "bubble sort" but a "selection
CB>GW>sort", and indeed selection sorts are generally quicker than Bubble
CB>Not really.  A few minor percent.  Same lousy N^2 growth rate.  All you
CB>are really doing is changing the 'O' very slightly, not the growth.
Oh yes, really! :-) It does depend on the time "cost" of comparisons and
exchanges but, in general, comparisons are quick while exchanges are
slow, and while a selection sort has at most N exchanges, a bubble sort
is average 1/4 (N^2 - N) and max 1/2 (N^2 - N).
A Selection sort always performs 1/2 (N^2 - N) comparisons, while this
is the upper bound on a bubble sort with early exit if there are no
exchanges is a pass. The early exit testing itself adds time though, so
there is no simple answer :-(. Given that comparisons are quick compared
to exchanges, a selection sort will generally be faster than a bubble
sort.
CB>Frankly, that change is so minor, I personally don't consider it to be a
CB>new algorithm, just a minor refinement to an old one.  (That's why I put
CB>it in tiny little quotes.)  I don't think changes that minor are worth
CB>giving it a new name.
That's like saying that parsnips and carrots are the same because they
are both root vegetables with a similar shape grown from seed.
While both sorts share the same basic loop structure, the operation is
totally different.
CB>The change I was meaning isn't what I normally consider an insertion
CB>sort.  (Something such as the one in snippets.)
Agreed. It is in no way related to insertion sorts.
CB>I just meant:
CB>for (loop1=0;loop1  {highest=loop1;
CB>   for (loop2=loop1+1;loop2      if (data[loop2] > data[highest]) highest=loop2;
CB>   if (loop1!=highest) swapdata(loop1,highest);
CB>  }
CB>Personally, I still consider it to be a bubble sort, it just reduces the
CB>number of exchanges to only 'size'.
But it is now a totally different family of sorts, a selection sort.
Even though the loop structure is the same...
CB>GW>CB>On small data sets (both quantity and size), the loop overhead 
(setup,
CB>GW>CB>iter, end, etc.) can have a significant impact.  Also, the quality 
f
CB>GW>CB>the code, the size of the items to compare/swap, the time it takes 

CB>GW>Seconded... (or thirded if David gets here first!)
CB>I remember one time, back in the late 80s, I guess, on an 8 bit micro, I
CB>was sorting about 30 moves generated in a chess program, and it was
CB>actually faster for me to use a simple bubble sort than use the
CB>quick-sort library routine.  I guess the library routine was just very
CB>poorly written or something, but in that case, it was actually faster to
CB>do a simpler, hardwired bubble sort.  Just goes to show that for
CB>atypical situations, you just have to try it and see.
Down at that number of elements, a dedicated sort should always beat the
generalised qsort() provided by the compiler, but that does not mean
that a simple bubble sort, or a selection sort such as you post above,
will be faster than a customised shell sort (which is an insertion sort)
or quickersort (which is an exchange sort).
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------