Why aren't we all speaking LISP now?

[Roy Smith]

"Delaney, Timothy" <tdelaney at avaya.com> wrote:
> Indeed, the point of teaching bubblesort is to teach *not to use*
> bubblesort. In general, teaching sorting algorithms is for learning about
> algorithms and why a good algorithm is so important.

I've taught bubble sort as an introduction to algorithms.  Even though it's 
generally considered to be a bad sorting algorithm, it's a very simple one 
and easy for students to grasp, and sorting is something that they're 
already familiar with.  They understand what it is that they're trying to 
do, and can see how the individual steps are moving them in that direction.  
Once they've written their bubble sort routines, they can immediately put 
it to use sorting their address books, or recipie files, or whatever.

It's a good introduction to the idea of algorithmic thinking, i.e. the 
ability to take a non-trivial task and break it down into a set of small, 
understandable, steps.

And, finally, as Timothy says, it's also is a good segue into the idea of 
algorithmic complexity.  The first time they try to sort a list of all the 
words in the dictionary, they discover what O(N^2) means!  If I tried to 
teach quicksort first, they would probably get lost in the details, and not 
understand why such a seemingly simple task was being made so complicated.

All that being said, bubble sort is actually a decent algorithm to use if 
you know ahead of time that the data is already almost completely sorted.  
For example, let's say I had a list of the batting averages of all the 
major league baseball players.  These don't change much from day to day (at 
least past the first few weeks of the season).  If I updated each player's 
stats to include today's games, and wanted to re-sort the list in order of 
batting average, bubble sort might be a reasonable algorithm to pick.