[lug] File modification

[Bear Giles]

> > P.S., anyone else interested in a citizen initiative to make
> > teaching bubble sorts a capital offense?  Quick sorts are easier
> > to teach...
> 
> Easier to teach?  Now that's the funniest thing I've heard all week.

Teaching (as opposed to first implementations)? Sure.

Here's a shuffled deck of cards.

Put the red cards to the left, the black cards to the right.

In the red pile, put the diamonds to the left, the hearts to the right.
In the black pile, do the same with the clubs and the spades.

In each of the four piles, put the numbered cards to the left, the
face cards to the right.

Do a selection sort for each of the eight piles

Now combine the sorted piles.  Numbered cards on top of face cards.
Diamonds on top of hearts.  Clubs on top of spades.  Reds on top of
blacks.

That's the essense of a quick sort.  You separate one pile into two,
then repeat.  Then you combine them again.

A selection sort is just as easy.  Look for the ace of diamonds, put
it aside.  Look for the two of diamonds.  Put it behind the ace.
Look for the three of diamonds....

Now try doing the same thing with a bubble sort.  You can do it, of
course, but it doesn't feel natural.  (Curiously, to me the bidirectional
bubble sort feels more natural than the unidirectional one.)  Even
the shell sort feels more natural - if it's a black card, throw it
hard to the right.  Then if it's a face card, toss it to the right.
Then the last few passes you just exchange neighboring cards.

Finally, there's always the radix sort.  Deal the deck into 13 piles -
here we have the aces, the twos, the threes, etc.  Sort each pile
separately into the four suits.  Deal one card off each pile in order,
repeat.  If your sort doesn't reorder equal entries, a variant of this 
makes it easy to implement primary and secondary sort keys.


Once you've seen the algorithms in action, it's a lot easier to
understand the implementation of the algorithms.  The problem is that
(historically) few classes have started out with something the students
can hold in their hands before jumping into the code.  Even diagrams
on a blackboard don't have the power of a brief lab exercise with a
deck of cards, or a stack of pennies and dimes, etc.