why python annoys me

[Tim Peters]

[Oliver Korpilla]
> Haskell Quicksort:
> qsort:: Ord a=> [a] -> [a]
> qsort [] = []
> qsort (x:xs) = [y | y <- xs, y <= x] ++ [x] ++ [y | y <- xs, y > x]
[Ben Wolfson]
> Python Quicksort:
>
> def qsort(L):
>     L = list(L)
>     if L == []:
> 	return []
>     x, xs = L[0], L[1:]
>     return qsort([y for y in xs if y<=x])+[x]+ \
>            qsort([y for y in xs if y>x])
>
> Though you'd be better off with a list's sort() method, of course.

And Oliver would be better off had he remembered to apply qsort to the
partitions too.

Should also mention that, if Hoare were dead, he'd be rolling over in his
grave at calling these things "quicksorts" <wink>:  they're quadratic-time
for an already-sorted list, do twice as many comparisons as "a real"
quicksort, and do gobs & gobs more data movement than a real qs.

That said, a functional approach remains the best way to get across the key
*idea* behind quicksort; it's curious that there's such a large gap between
that and effective quicksort practice.  Also interesting to note that Hoare
wasn't familiar with recursion at the time he dreamed up quicksort (around
1960), and reported struggling both to explain the method to colleagues, then
to convince them it was correct.  The original description drew attention to:

    a unique data structure called a nest, which has the property
    that the last thing put in is the first thing taken out.

if-anyone-had-been-paying-attention-we'd-be-"popping-nests"-
    today<wink>-ly y'rs  - tim