On Mon, 3 Dec 2001, Tony Duell wrote:
> 'Bubble Sort' has nothing to do with bubble memory. Bubble sort is a
> well-known, very poor, sorting algorithm -- so poor that one book I have
> contains the quote (from memory) 'If you know what a bubble sort is, wipe
> it from your mind. If you don't, make a point of never finding out' :-)
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_at_xenosoft.com
Received on Mon Dec 03 2001 - 17:23:03 GMT