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