-- Zoom.Quiet [2004-08-11 17:21:08]

# 在三行代码中展示Quicksort

2.12 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:

```   1 def qsort(L):
2     if len(L) <= 1: return L
3     return qsort([lt for lt in L[1:] if lt < L]) + L[0:1] + \
4            qsort([ge for ge in L[1:] if ge >= L])
```

```   1 qsort [] = []
2 qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_ge_x
3                  where
4                    elts_lt_x = [y | y <- xs, y < x]
5                    elts_ge_x = [y | y <- xs, y >= x]
```

Here's a test function for the Python version:

```   1 def qs_test(length):
2     import random
3     joe = range(length)
4     random.shuffle(joe)
5     qsJoe = qsort(joe)
6     for i in range(len(qsJoe)):
7         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 href=http://www.haskell.org/aboutHaskell.html.>http://www.haskell.org/aboutHaskell.htm l. 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(N2) 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?

list内涵在python2.0被介绍，所以这个配方的代码在早期的版本并不工作。但是，你不会用一个?br>芏嗄暌郧暗膒ython来展示它给你的朋友，对吗？

A less compact version with the same architecture can easily be written to use named local variables and functions for enhanced clarity:

```   1 def qsort(L):
2     if not L: return L
3     pivot = L
4     def lt(x, pivot=pivot): return x<pivot
5     def ge(x, pivot=pivot): return x>=pivot
6     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.