Bubble sorts have their place (was: FLUKE?

On Mon, 3 Dec 2001, Tony Duell wrote: Then that author is an idiot! There are, indeed, MANY situations where a bubble sort is the WRONG one to choose, and therefore would be bad. And, admittedly more situations where it is the WRONG choice than situations where it is the RIGHT choice. BUT, there are a few situations where a bubble sort is significantly superior to all of the "better" sort algorithms. 1) situations of N elements to be sorted, to be presented/displayed R at a time. For example: the sort that e-bay does. A bubble sort (often RIGHT TO LEFT) can select the first R items in a maximum of R passes. Then WHILE you are looking at the first R "5.25 head cleaning" kits, it can be sorting the next R or more. or, with a bibliographic database, such as a library OPAC (Online Public Access Catalog), it can present the first R elements, and sort the rest while you are still absorbing the initial result set. Other, "better" sort algorithms will sort the entire database MUCH faster, but can't display the first R items until AFTER finishing sorting the entire database. 2) taking advantage of existing order. A "better" sort, such as Shell/Metzner, takes the same amount of work to sort regardless of whether the data is a little out of order, or totally random. (BTW, computer Science profs typically are incapable of understanding that not all data to be sorted is completely random, and they base everything that they teach on the premise that the data to be sorted is completely random.) But sometimes there is a need to "re-sort" data that was once in order, but has had additions, changes, or corruptions that have resulted in only part of it being out of order. For example, property records that are alphabetically sorted, but need to be resorted because SOME of the "Owner name" fields have been changed due to transfers. Or, sometimes there is data that is sorted by one field, and needs to be sorted by another field that has a partial correlation with the prior sort field. For example, a DMV file that was sorted by age, but now needs to be sorted by how long somebody has had a driver's license. A bubble sort that alternates between LEFT TO RIGHT and RIGHT TO LEFT (sometimes known as a "Shaker Sort") does better than any other available algorithm at taking advantage of existing order, and can re-establish order with a maximum number of passes equal to the number of elements that were out of place. Meanwhile, the "better" sort is busy resorting the entire database unnecessarily. The bubble sort, is also the EASIEST to implement for a beginning student (hopefully followed, within the hour, by other algorithms.) -- Grumpy Ol' Fred cisin(a)xenosoft.com