Bubble sorts have their place (was: FLUKE?

From: Fred Cisin <cisin_at_xenosoft.com>
Date: Tue Dec 4 00:04:55 2001

On Tue, 4 Dec 2001, Tony Duell wrote:
> > > 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 a few things that I disagree with in 'Numerical Recipies', but
> I certainly wouldn't call the authors 'idiots'!

OK, ANYBODY can say something idiotic.
His comment about bubble sort, and mine about him were equally overly
intense.

> > 1) situations of N elements to be sorted, to be presented/displayed R at
> > a time.
> This may well be true, but I am not going to accept that there are no
> other sorting algorithms with this property, at least not without a lot
> of thought.

I can't claim that none exist, (and some sort of selection based sort
seems feasable), but I've never seen anything but variations of bubble
sort that provide for being able to get intermediate results without
waiting for completion of the entire sort.

> > 2) taking advantage of existing order. A "better" sort, such as
> Often in this sort of case you know the items that are out of order.
> Either you're adding a few more items to the database, or you know that
> some items have changes. And, assuming the database is some kind of
> linked list (so that moving iterms around is simple -- just move the
> pointers), it would seem to be simpler just to take those items you know
> to be sorted and then to search for the right point to insert each new
> item.

How about a case where data is nominally in order, but human beings have
had their hands on the data? Such as retrospective conversion of a
library card catalog through automated scanning and OCR. It is ALMOST in
order, but there are mistakes.


> > Science profs typically are incapable of understanding that not all data
> > to be sorted is completely random, and they base everything that they
> Comparison of sorting algorithms generally includes (at least) the cases:
> List in the right order ; List in reverse order ; One item out of order ;
> Random order.

That is certainly better than much of what I've seen in higher
education. Note that cases 1 and 3 will favor a properly written bubble
sort over "better" algorithms.

> > The bubble sort, is also the EASIEST to implement for a beginning student
> > (hopefully followed, within the hour, by other algorithms.)
> I have never been a believer in teaching something because it's simple.
> I've beem on the wrong end of problems caused by simplifying things too
> far....

There are certainly many problems associated with over-simplification.
OTOH, sometimes it can help a lot with understanding of concepts to reduce
the number of variables, at least temporarily.

> OK, I'll admit it. I've used a bubble sort -- I had a list of 5 items to
> sort, no sort routine in the standard library, and run time was not that
> important. A bubble sort seemed to make sense there.

It IS easy to implement!


> So the original statement was a little strong, sure. But equally, I've
> seen the bubble sort be used in far too many places where it was the
> wrong choice...

I've seen both.
I've seen "programmers" who insist on using "better" algorithms when a
bubble sort would be the right choice.
OB_e-bay_bashing: WHY does it take SO long for e-bay to display the first
R items from a search?
And I've seen bubble sorts used when they were inappropriate, or worse
yet, a bubble sort going from left to right, when right to left was called
for - that creates the worst case scenario that gives a bubble sort its
bad reputation.


The most important thing that I teach in "Data Structures and Algorithms"
is that there are no "good" or "bad" algorithms; that what counts is
selecting the most appropriate one for the specific situation. The best
thing that I can say about my teaching is that a significant number of my
students become better than I am.


--
Grumpy Ol' Fred        cisin_at_xenosoft.com
Received on Tue Dec 04 2001 - 00:04:55 GMT

This archive was generated by hypermail 2.3.0 : Fri Oct 10 2014 - 23:33:37 BST