2.12 Showing Off Quicksort in Three Lines

Credit: Nathaniel Gray

2.12.1 Problem

You 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 Solution

Functional 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 Discussion

This 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 sort is of course much faster and should always be preferred. The only proper use of this recipe is for impressing friends, particularly ones who (quite understandably) are enthusiastic about functional programming, and particularly about the Haskell language.

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²) performance for the very common case of sorting an already-sorted list, so you would never want to do this in production code. Because this is just a propaganda thing, though, it doesn't really matter.

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 from _ _future_ _ import nested_scopes) and later, you can do without the pivot=pivot trick in the formal argument lists of lt and ge.

2.12.4 See Also

The Haskell web site (http://www.haskell.org).