Hi Carey,
You wrote to David Noon:
CB>DN>Hence, my consistent statements about Insertion sort being typically 
twic
CB>DN>as fast as Bubble sort. Since the exchanges are the CPU hogs and, 
etter
CB>DN>still, Insertion sort uses moves instead of exchanges,
CB>DN>the ratio is actually
CB>DN>a conservative one.
CB>I don't want to get into what sort routine is the best for small arrays
CB>(or what 'small' means or on what particular data, compiler, language,
CB>implementation, etc.), but I do think it should be pointed out that
CB>comparisons and exchanges aren't really the whole story. (I should also
CB>point out that with most real 'bubble sorts', there will only be 'n'
CB>exchanges.  Most implementations will find the highest/lowest and then
CB>exchange in the outer loop, rather than in the inner on every successful
CB>comparisons.  [Well, the 'highest' will be set, but that's very
CB>different from exchanging, esp. when the data is large structures.])
I'm glad you said 'bubble sort', because as soon as you change to the
method you describe it is no longer a "bubble sort" but a "selection
sort", and indeed selection sorts are generally quicker than Bubble
sorts. The disadvantage is that a correctly written selection sort will
always make 1/2 * (N**2 - N) comparisons, there is no way round that
without changing to another algorithm.
CB>On small data sets (both quantity and size), the loop overhead (setup,
CB>iter, end, etc.) can have a significant impact.  Also, the quality of
CB>the code, the size of the items to compare/swap, the time it takes to
CB>compare, etc. all play a major roll in small data sets.  When the cost
CB>of exchanging is much larger than doing the comparison (like with a
CB>struct, etc.) it can often be worth doing a few more comparisons to
CB>reduce the number of exchanges you have to do.
Seconded... (or thirded if David gets here first!)

I agree with the sentiments of the rest of your posting. Indeed my
interest is in sorting a fairly large data set (5000 or 10000 items
where the size of an item is 2k), and looking at ways of presenting the
data to the customer in sequences sorted on different fields. This _has_
to be done by sorting pointers to the data as for system performance
reasons (this is "real time" - as in quick response) magnetic card
control system where the index into the database is stored on the
magnetic card so that I can get to the record to load for
checking/update without any intermediate look up stages.
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------