Go rant

[Kevin Bealer]

Don Wrote:
> retard wrote:
...
> 
> I'd say it's easier. If you watch someone sorting some cards, they'll 
> use either insertion sort or selection sort. Nobody should have ever 
> heard of bubble sort, I'm pleased to hear some schools aren't mentioning 
> it. Such a foolish algorithm.
> 
> "the bubble sort seems to have nothing to recommend it, except a catchy 
> name " - Knuth.

(Non-software) people doing routine tasks often come up with better algorithms intuitively than my intuition expects them to.

I think a lot of people would do even better than insertion with a deck of poker cards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together.  If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort.

I think when you ask people to do a computer version of how they would sort, they do worse than this.  It's so hard to communicate anything complicated to a computer that they instinctively "dumb it down" and do insertion or bubble.  Insertion is what you would manually use when dealing with adding a few new elements to a short stack, whereas something like a bubble might be what you would use manually when it's hard to jump around among the elements of the sequence (e.g. if you have a bunch of "see also" references embedded in dictionary entries and you need to sort within the see-also 'chain').  That approach (kind of) matches the claims often given by computer programmers that bubble sort is good for linked lists and/or "only fixing a few things that are out of place in a mostly sorted list".

When you have a pupil that is as hard to talk to and unmotivated to learn as a computer, the first attempt is to try to teach it anything at all and call that a success if it works.  A more eager human pupil tries to meet you half way, so you naturally respond and take pleasure in teaching them more and more advanced stuff.  If you're really hard headed and immune to tedium, you keep trying with even a super-dumb pupil like a CPU.  You keep going in for the hard case so many times that you and eventually major in CompSci out of habit.

Kevin