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

At 12:58 AM 12/4/01 +0000, you wrote: I've used it just a few days ago, while ordering the row indexes of elements in each column of the incidence matrix of _very large_ networks. However, these networks are very sparsely connected, with usually just two connections per node, and the average number of connections per node is 2.3-2.6 . This means that in most cases a bubble sort will swap data at most once for each column. Definitely the best algorithm for the problem at hand. carlos. -------------------------------------------------------------- Carlos E. Murillo-Sanchez carlos_murillo(a)nospammers.ieee.org

On Mon, 3 Dec 2001, Tony Duell wrote: You can cut 50% off by: In each pass, compare first and second, second and third, etc ... up to comparison of item N - number of passes. It worst case situation, you can save one pass by stopping when you've done N-1 passes, even if that last pass did have a swap.