I l@ve RuBoard |

## 2.12 Showing Off Quicksort in Three LinesCredit: Nathaniel Gray ## 2.12.1 ProblemYou need to show that Python's support for the functional programming paradigm is quite a bit better than it might seem at first sight. ## 2.12.2 SolutionFunctional programming languages, of which Haskell is a great example, are splendid animals, but Python can hold its own in such company: def qsort(L): if len(L) <= 1: return L return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + \ qsort([ge for ge in L[1:] if ge >= L[0]]) In my humble opinion, this is almost as pretty as the Haskell version from http://www.haskell.org: qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_ge_x where elts_lt_x = [y | y <- xs, y < x] elts_ge_x = [y | y <- xs, y >= x] Here's a test function for the Python version: def qs_test(length): import random joe = range(length) random.shuffle(joe) qsJoe = qsort(joe) for i in range(len(qsJoe)): assert qsJoe[i] == i, 'qsort is broken at %d!'%i ## 2.12.3 DiscussionThis is a rather naive implementation of quicksort that illustrates
the expressive power of list comprehensions. Do not use this in real
code! Python's own built-in I cooked up this function after finding the wonderful Haskell quicksort (which I've reproduced above) at http://www.haskell.org/aboutHaskell.html. After marveling at the elegance of this code for a while, I realized that list comprehensions made the same thing possible in Python. Not for nothing did we steal list comprehensions right out of Haskell, just Pythonizing them a bit by using keywords rather than punctuation! Both implementations pivot on the first element of the list and thus
have worst-case O(N List comprehensions were introduced in Python 2.0, so this recipe's code will not work on any earlier version. But then, you wouldn't be trying to impress a friend with a many-years-old version of Python, right? A less compact version with the same architecture can easily be written to use named local variables and functions for enhanced clarity: def qsort(L): if not L: return L pivot = L[0] def lt(x, pivot=pivot): return x<pivot def ge(x, pivot=pivot): return x>=pivot return qsort(filter(lt, L[1:]))+[pivot]+qsort(filter(ge, L[1:])) This one works on old and crusty Python versions, but in Python 2.1
(with a ## 2.12.4 See AlsoThe Haskell web site (http://www.haskell.org). |

I l@ve RuBoard |