Why aren't we all speaking LISP now?

Sheila King sheila at spamcop.net
Sat May 12 04:38:46 CEST 2001


On Fri, 11 May 2001 07:10:06 -0400, Roy Smith <roy at panix.com> wrote in
comp.lang.python in article <roy-C59972.07100611052001 at news1.panix.com>:

: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.

I taught Bubble Sort to my ap computer science class last year. I was familiar
with it, and I didn't realize that it was no longer on the list of required
topics for the exam. But it was a successful lesson, and the students understood
it. Yes, it was easy.

The problem was, that they were required to learn Selection Sort, Insertion
Sort, Quick Sort and Merge Sort for the exam. After seeing Bubble Sort, they
didn't feel like wrestling with the ideas of how the other sorts worked. They
were satisfied that they had one algorithm that worked. I guess that means they
weren't real "computer scientists". Well, I don't blame them. They were high
school students who had little or no idea what "computer science" was, when they
signed up for the course.

Anyhow, this year I decided to forgo Bubble Sort altogether and started with
Selection Sort. You know, it really is a simple algorithm, also.

: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.

Oh, of course don't teach QuickSort first!

By the way, for anyone teaching sorting algorithms, I've found that a visual
demonstration helps the students to understand what is going on immensely. I
have a collection of links to web sites with Java applet animations of Sorting
Algorithms. This is how I introduce Merge Sort and Quick Sort. I let them see
the visual demonstration first and have them explain in their own words, how the
algorithm works, and to sort on paper, a vector (it's a C++ class) using the
different algorithms. When they have that down, then we look at the code.

Here is my web page with the collection of links, if this is interesting to
anyone:
http://www.thinkspot.net/materdei/apcompsci/SearchandSortAlgos/index.html

--
Sheila King
http://www.thinkspot.net/sheila/
http://www.k12groups.org/






More information about the Python-list mailing list