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

[Gareth McCaughan]

Stefan Axelsson wrote:

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

In Python it's

def sort(xs):
  xs = xs[:]
  xs.sort()
  return xs

which is just as doable from memory and likely to be much faster
and less wasteful of memory. :-)

Seriously: yes, that Haskell code is very elegant. But it's
not a good sorting routine. Consider the behaviour if you
hand it an already-sorted list; observe that it traverses
the input twice when it need do so only once; see how much
unnecessary memory it allocates. If you use Haskell to
write a *real*, production-quality, sorting routine, does
it actually come out any better than Python?

Some languages (I shan't start a flame war by naming them
here) are painstakingly optimized to make it easy to
almost-solve problems with them. I don't think that's
a good way to be...

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
.sig under construc