GW>CB>comparisons and exchanges aren't really the whole story. (I should also
GW>CB>point out that with most real 'bubble sorts', there will only be 'n'
GW>CB>exchanges.  Most implementations will find the highest/lowest and then
GW>I'm glad you said 'bubble sort', because as soon as you change to the
GW>method you describe it is no longer a "bubble sort" but a "selection
GW>sort", and indeed selection sorts are generally quicker than Bubble
Not really.  A few minor percent.  Same lousy N^2 growth rate.  All you
are really doing is changing the 'O' very slightly, not the growth.
Frankly, that change is so minor, I personally don't consider it to be a
new algorithm, just a minor refinement to an old one.  (That's why I put
it in tiny little quotes.)  I don't think changes that minor are worth
giving it a new name.
The change I was meaning isn't what I normally consider an insertion
sort.  (Something such as the one in snippets.)
I just meant:
for (loop1=0;loop1 data[highest]) highest=loop2;
   if (loop1!=highest) swapdata(loop1,highest);
  }
Personally, I still consider it to be a bubble sort, it just reduces the
number of exchanges to only 'size'.
GW>CB>On small data sets (both quantity and size), the loop overhead (setup,
GW>CB>iter, end, etc.) can have a significant impact.  Also, the quality of
GW>CB>the code, the size of the items to compare/swap, the time it takes to
GW>Seconded... (or thirded if David gets here first!)
I remember one time, back in the late 80s, I guess, on an 8 bit micro, I
was sorting about 30 moves generated in a chess program, and it was
actually faster for me to use a simple bubble sort than use the
quick-sort library routine.  I guess the library routine was just very
poorly written or something, but in that case, it was actually faster to
do a simpler, hardwired bubble sort.  Just goes to show that for
atypical situations, you just have to try it and see.
--- QScan/PCB v1.19b / 01-0162
---------------