Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cornell!uw-beaver!uw-june!pattis
From: pattis@cs.washington.edu (Richard Pattis)
Newsgroups: comp.edu
Subject: Re: ALGORITHMS ANYBODY?
Message-ID: <12868@june.cs.washington.edu>
Date: 23 Aug 90 02:29:56 GMT
References: <90Aug22.090345edt.9450@neat.cs.toronto.edu> <1990Aug22.182415.27036@newcastle.ac.uk>
Organization: U of Washington, Computer Science, Seattle
Lines: 51
Summary: In defense of bubble sort

In article <1990Aug22.182415.27036@newcastle.ac.uk>, Chris.Holt@newcastle.ac.uk (Chris Holt) writes:
> DON'T use bubble sort; once people learn it, they use it for the
> rest of their lives, it seems like, and it takes ages to unteach.
> 
> You might try a pattern matching (string search) algorithm (it's got a
> simple specification); and the old matrix multiplication is a
> good one to start arrays with.
> 

What exactly is wrong with bubble sort? It is the smallest sorting algorithm
to state (in most imperative programming languages), and is the easiest one
to prove correct (assuming a Swap procedure). For small array sizes, its
performance is just fine.  If a student ever has to reconstruct a sorting
method from scratch, he/she will have the highest probability of getting
bubble sort right (higher than any other algorithm I can think of).  There
are even sets of data (almost sorted) where bubble sort can do better than
many "asymptotically faster" sorting algorithms.

So, do I teach bubble sort in my CS-1 class?  Yes.  How do I ensure they
won't use it in subsequent programs? By the end of the class my students have
learned about generic subprograms (I teach Ada) and they are presented with
various N**2 and NLogN generic sorting procedures; all are instantiated in
exactly the same way (element type, array type, comparison function).

In all their CS-2 programs, wherever sorting is required, they instantiate
whatever sorting subprogram they want (and can easily change their mind about
the decision later). In this course we have them compute approximate values
for the constants of all these subprograms, and predict running times on
large data (so they understand bubble sort's weakness).  We also teach them
how to use program profilers, to try to understand where the majority of
time is spent in a system.

If they ever go to a new language/system that doesn't have such built-in
sorting procedures, and they really need to write their own from scratch
(no books) I'd be happy if they wrote bubble sort. If the problems they had
to solve had a large amount of data, and sorting was the bottleneck, they
would know about other algorithms, and I hope be able to transcribe them from
some source to the particular language/system.

I guess the bottom line is that I don't think it takes more than 2 quarters
to give students a good perspective on sorting algorithms in software
systems.


Back to the main topic: Sedgewick's book, "Algorithms" is a great place to
get string algorithms.  The most recent CACM had a few variants on these.
Boolean matrix multiplication for path problems or solving stochastic
systems can be presented in a realistic manner.


Rich Pattis