Recipe5.11.Showing off quicksort in Three Lines

Recipe 5.11. Showing off quicksort in Three Lines

Credit: Nathaniel Gray, Raymond Hettinger, Christophe Delord, Jeremy Zucker

Problem

You need to show that Python's support for the functional programming paradigm is 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 code is almost as pretty as the Haskell version from http://www.haskell.org:

qsort [  ] = [  ] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x                  where                    elts_lt_x = [y | y <- xs, y < x]                    elts_greq_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 rather naive implementation of quicksort illustrates the expressive power of list comprehensions. Do not use this approach in real code! Python lists have an in-place sort method that is much faster and should always be preferred; in Python 2.4, the new built-in function sorted accepts any finite sequence and returns a new sorted list with the sequence's items. 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 in the "Solution") 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 approach 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. You would never want to do so in production code! Because this recipe is just a propaganda piece, though, it doesn't really matter.

You can write a less compact version with similar architecture in order to use named local variables and functions for enhanced clarity:

def qsort(L):     if not L: return L     pivot = L[0]     def lt(x): return x<pivot     def ge(x): return x>=pivot     return qsort(filter(lt, L[1:]))+[pivot]+qsort(filter(ge, L[1:]))

Once you start going this route, you can easily move to a slightly less naive version, using random pivot selection to make worst-case performance less likely and counting pivots to handle degenerate case with many equal elements:

import random def qsort(L):     if not L: return L     pivot = random.choice(L)     def lt(x): return x<pivot     def gt(x): return x>pivot     return qsort(filter(lt, L))+[pivot]*L.count(pivot)+qsort(filter(gt, L))

Despite the enhancements, they are meant essentially for fun and demonstration purposes. Production-quality sorting code is quite another thing: these little jewels, no matter how much we dwell on them, will never match the performance and solidity of Python's own built-in sorting approaches.

Rather than going for clarity and robustness, we can move in the opposite direction to make this last point most obvious, showing off the obscurity and compactness that one can get with Python's lambda:

q=lambda x:(lambda o=lambda s:[i for i in x if cmp(i,x[0])==s]:             len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x)( )

At least, with this beauty (a single logical line, although it needs to be split into two physical lines due to its length), it should be absolutely obvious that this approach is not meant for real-world use. The equivalent, using more readable def statements rather than opaque lambdas, would still be pretty obscure:

def q(x):     def o(s): return [i for i in x if cmp(i,x[0])==s]     return len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x

but a little more clarity (and sanity) can be recovered by opening up the pithy len(x)>1 and . . . or x into an if/else statement and introducing sensible local names again:

def q(x):     if len(x)>1:         lt = [i for i in x if cmp(i,x[0]) == -1 ]         eq = [i for i in x if cmp(i,x[0]) == 0 ]         gt = [i for i in x if cmp(i,x[0]) == 1 ]         return q(lt) + eq + q(gt)     else:         return x

Fortunately, in the real world, Pythonistas are much too sensible to write convoluted, lambda-filled horrors such as this. In fact, many (though admittedly not all) of us feel enough aversion to lambda itself (partly from having seen it abused this way) that we go out of our way to use readable def statements instead. As a result, the ability to decode such "bursts of line noise" is not a necessary survival skill in the Python world, as it might be for other languages. Any language feature can be abused by programmers trying to be "clever" . . . as a result, some Pythonistas (though a minority) feel a similar aversion to features such as list comprehensions (since it's possible to cram too many things into a list comprehension, where a plain for loop would be clearer) or to the short-circuiting behavior of operators and/or (since they can be abused to write obscure, terse expressions where a plain if statement would be clearer).

Recipe5.11.Showing off quicksort in Three Lines