GW>exchanges is a pass. The early exit testing itself adds time though, so
GW>there is no simple answer :-(. Given that comparisons are quick compared
Right.
GW>to exchanges, a selection sort will generally be faster than a bubble
GW>sort.
Maybe.  Generally.  You can't be sure until you test.  Which is what I
was originally pointing out.
GW>CB>Frankly, that change is so minor, I personally don't consider it to be 

GW>CB>new algorithm, just a minor refinement to an old one.  (That's why I 
ut
GW>CB>it in tiny little quotes.)  I don't think changes that minor are worth
GW>CB>giving it a new name.
GW>That's like saying that parsnips and carrots are the same because they
GW>are both root vegetables with a similar shape grown from seed.
More like saying different brands of beer are alike.  Once you get rid
of the cans and fancy logos, they all taste alike, and anything more
than an occasional sip is going to make you puke, and _nobody_ is going
to mistake even the best can/bottle/mug of beer for a good wine or
even a decent soft drink!
When you are talking about dung, what difference does it make what
animal it came from.  It's still going to smell the same.
GW>CB>Personally, I still consider it to be a bubble sort, it just reduces 
he
GW>CB>number of exchanges to only 'size'.
GW>But it is now a totally different family of sorts, a selection sort.
GW>Even though the loop structure is the same...
But it's performance is still O(N^2).
And, no, it's not a new family.
A _NEW_ family means it's not a simple, incredibly minor modification to
another family.  They may not be the exact same algorithm, but they are
definitely related and in the same family.  When you can make a change
that minor, it doesn't instantly become a new algorithm.
GW>CB>I remember one time, back in the late 80s, I guess, on an 8 bit micro, 

GW>CB>was sorting about 30 moves generated in a chess program, and it was
GW>CB>actually faster for me to use a simple bubble sort than use the
GW>CB>quick-sort library routine.  I guess the library routine was just very
GW>CB>poorly written or something, but in that case, it was actually faster 
o
GW>CB>do a simpler, hardwired bubble sort.  Just goes to show that for
GW>CB>atypical situations, you just have to try it and see.
GW>Down at that number of elements, a dedicated sort should always beat the
GW>generalised qsort() provided by the compiler, but that does not mean
GW>that a simple bubble sort, or a selection sort such as you post above,
GW>will be faster than a customised shell sort (which is an insertion sort)
GW>or quickersort (which is an exchange sort).
I never said it would, etc.
What I've said, in the few messages I wrote, was that there is a lot
more to picking a 'best' sort than just doing the O().
Going solely by the 'Big Oh', the qsort would have then and _always_
been a better choice.  But it wasn't true.
As I was saying before, and then when I gave that example, for unusual
situations or small data sets, or extremely large data sets, the Big Oh
is not 'written in stone'. For unusual situations or small data sets,
there are other factors that are as important as the overall growth.  A
simple difference between the code quality of one sort vs. another, or
how well a the optimizer handles one code vs. the other can impact the
overall run time enough that the sort with the worse O() growth can
actually be better than the other.  For extremely large data sets, the
data organization and disk access times, etc. can be important enough to
influence which algorithm is best.  (Consider using a tape/merge sort
vs. a carefully written  which depends on
random access of the data.)
--- QScan/PCB v1.19b / 01-0162
---------------