Bubblesort (was: Re: Why aren't we all speaking LISP now?)

[Stefan Axelsson]

In article <roy-C59972.07100611052001 at news1.panix.com>,
Roy Smith  <roy at panix.com> wrote:

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

I was going to keep quiet since I'm going away for the week and won't
be here to keep the argument going, but I cannot hold my peace! ;-)

In Haskell a quick sort is:

qsort []     = [] 
qsort (x:xs) = qsort[y | y <- xs, y < x] ++ [x] ++ qsort[y | y <- xs, y >= x] 

Evidently doable from memory... And the above code could well be read
out aloud and make sense, almost even to a rank beginner. 

  "An empty list is already sorted, otherwise to sort a list prepend
  all elements that are smaller than the first with the first element,
  and append all elements that are greater than the first elements to
  the first elements. Of course you must sort the smaller and greater
  elements before concatenating them into a list, since the list
  wouldn't be sorted otherwise!"

I'm sure that something equally elegant could be accomplished in
Python (though I'm too new to Python I'm afraid), it has the
prerequisites (list comprehension, lists etc), which is why I didn't
feel too bad about the above Haskell code. It'd be a bit insulting an
comp.lang.c for example ;-) ;-)

The moral: it's not that HLL:s have sorting built in, it's that they
enable you to express powerful concepts without being mired in
detail. (Which incidentally, and IMHO, is why students always cry help
when exposed to functional programing, the easy stuff that lasts a
whole course on imperative programming is finished off in a few weeks,
and then the real fun begins. ;-)

P.S. And yes, for a practical application choosing the first element
as the pivot element isn't perhaps the smartest course of action, the
list could already be sorted for example.
 
Stefan,
-- 
Stefan Axelsson     (For mail address see: http://www.ce.chalmers.se/staff/sax)