Bubble sorts and such-like

[Seaman]

>  A bubble sort is the fastest means possible to sort an already-sorted list 
>  (order n, even omega n!).  

Please explain how the bubble sort is faster than the insertion sort for
an already-sorted list.

The bubble sort requires...
  n-1 comparisons
  0   exchanges.

The insertion sort requires...
  n-1 comparisons
  0   exchanges.

>  I just like the clean and simple implementation it allows and it is easy to 
>  explain to people in a couple of minutes.

Insertion sort is cleaner and simpler and easier to explain, besides being
faster.  If you don't believe it, write down the loop invariants for the
two algorithms and see which one is simpler.  You might also compare the
diagrams which Knuth used to illustrate the two sorts and see which is
simpler.

"The teaching of bubble sorts ought to be considered a criminal offense."
-- 

Dave Seaman			"My hovercraft is full of eels."
..!pur-ee!pucc-i:ags