## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required