Originally Posted by

**MK27**
A lot of what I have read about comparative sorting on the web has been, I think, regurgitated to the point where the regurgitator has a hard time finding reality.

I don't really understand the formulas used to express the efficiency of the algorithms, but I do understand the algorithms themselves in so far as they are applied in programming. I believe the O(n^2) etc style measurements of efficiency are actually based on a mathematical abstraction of the method ("algorithm") AND NOT statistical measurement of how the method performs in practice. (In other words, this is someone's deductive reasoning and not an empirical observation). After all, you could write a sort according to the algorithm and then average or measure the number of comparisons it makes. But that IS NOT how these formulas (eg. O(n^2)) came into being, and the actual logic of them is not always made apparent.

For example, a normative statement about the bubble sort is that "bubble sort always performs n-1 passes through the data, period. Its best case and worst case behaviors are completely identical". I actually have several charts and tables of formuli that all say this, sometimes vehemently, and I imagine they all actually have the same source somewhere in time and space, which is never referenced because they *appear* to rest on the authority of deductive reasoning. Yet in practice this statement about bubble sort CANNOT BE TRUE.

In practice, a flag is used to indicate the completion of a sort. Bubble sort passes thru data one item at a time and swaps it forward if it's value is higher than the next item. If, after a pass, nothing has changed, the sort is done.

That means by definition bubble sort will make a variable number of passes. If the list is already sorted (a best case), then you have n-1 passes.

Selection sort, which works by moving lowest values one at a time, will always have the same number of passes since it proceeds the same way regardless. So with an badly unsorted list it will tend to do better than bubble sort, but if the list is only slightly out of order, bubble sort will do much, much better, making a comparable number of passes and comparisons to a merge sort.

So regurgitating these "measurements" out of a textbook tends to imply ??what?? about some of the computer science clergy, iMalc.

I guess it all amounts to the same thing anyway. A merge sort is better than a selection sort is better than a bubble sort, etc.