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(a)xenosoft.com