[comp.edu] "Bubble" sorts

harmon_b@husc2.UUCP (03/12/87)

	If by "bubble sort" you are talking about the same sort I am
(where one comparision/swap "finger" repeatedly sweeps the data), there
is a variation which I happen to like because I re-invented it before I
found out what it was called.  I am now told it is called the shaker
sort, and all it does is make that "finger" stroke alternately up and
down.  This prevents the problems where one item is far away from its
place in the wrong (front end of stroke) direction.  The worst case is
still reverse order, but almost-sorted lists now reliably approach O(n).
I happen to consider this the perfect companion to the quicksort, since
each does best where the other does worst.  A fast test may be able to
indicate which is better at run-time, or you can (as always) pick
between them when writing, based on foresight.


	Dave