Python Cookbook

Showing Off Quicksort in Three Lines

Credit: Nathaniel Gray

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.

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

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