Welcome, guest | Sign In | My Account | Store | Cart
2

OK, 4 lines if you count wrapped lines. :^) This is a rather naive implementation of quicksort that illustrates the expressive power of list comprehensions. DO NOT USE THIS IN REAL CODE!

NOTE: Due to an annoyance in the ASPN submission filters you must manually remove the space after the '\' character in the third line if you intend to use the code. Otherwise you will get a syntax error.

Python, 21 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def qsort(L):
    if len(L) <= 1: return L
    return qsort( [ lt for lt in L[1:] if lt < L[0] ] )  +  \ 
              [ L[0] ]  +  qsort( [ ge for ge in L[1:] if ge >= L[0] ] )


# IMHO this is almost as nice as the Haskell version from 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]

# And here's a test function:
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!'

I cooked up this function after finding the wonderful Haskell quicksort at http://www.haskell.org/aboutHaskell.html (which I've reproduced above). After marvelling at the elegance of this code for a while I realized that list comprehensions made the same thing possible in Python!

Both implementations pivot on the first element of the list and thus have worst-case performance for the very common case of sorting an already-sorted list. You would never want to do this in production code! Since this is just a recreational excercise, though, it doesn't really matter. :-)

Since list comprehensions were introduced in Python 2.0 this code will not work on any earlier version.

8 comments

Nathan Gray (author) 15 years, 9 months ago  # | flag

Continuation character dropped. It looks like the "\" continuation character was dropped from the code and my third and fourth lines were combined. I guess it really is quicksort in 3 lines!

FYI, the third and fourth lines should have looked like:

return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) +         [ L[0] ] + qsort( [ ge for ge in L[1:] if ge >= L[0] ] ).

ASPN, you may want to fix this problem, since line continuations are common in python. (Be aware that the "\" shows up in the preview).

Nathan Gray (author) 15 years, 9 months ago  # | flag

Sigh. Yes, the "\" was dropped again from the above comment. I give up. :-(

Nathan Gray (author) 15 years, 9 months ago  # | flag

Success! (Sort of). It looks like

"\ "

is not interpreted as line continuation by the ASPN filters. Alas, the end-user now has to manually delete the space if she wants to run the code, so I've added a note to the description.

Raymond Hettinger 15 years, 3 months ago  # | flag

Refinements. Here is a slightly less naive version. Pivot selection is random to make worst case performance less likely. Pivots are counted to handle degenerate cases with many equal elements. Filter is used for rapid partitioning.

def qs(ds):
    if len(ds) &lt;= 1: return ds
    pivot = random.choice(ds)
    return qs(filter(lambda x: x &lt; pivot, ds)) +
           [pivot]*ds.count(pivot) +
           qs(filter(lambda x: x > pivot, ds))
Christophe Delord 14 years, 9 months ago  # | flag

Just For Fun: Quicksort in 1 Line. Of course this must not be used in real code too!

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)()

This lambda expression is just a rewriting of this function:

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) + q(eq) + q(gt)
    else:
        return x
Jeremy Zucker 14 years, 4 months ago  # | flag

Bug in quicksort long form...

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) + q(eq) + q(gt)
    else:                  ^^^^^
        return x

Running q(eq) will infinitely recurse. Use eq instead of q(eq)

Dave Edwards 12 years, 10 months ago  # | flag

Misprinted in O'Reilly's _Python Cookbook_. O'Reilly's _Python Cookbook_ published this recipe without the second list comprehension [ L[0] ]. It looks like:

def qsort(L):
    if len(L) O'Reilly's _Python Cookbook_ published this recipe without the second list comprehension [ L[0] ].  It looks like:

<pre>
def qsort(L):
    if len(L)

</pre>

Dave Edwards 12 years, 10 months ago  # | flag

Correction. This site's markup is unfathomable.

O'Reilly published this recipe as

def qsort(L):
    if len(L) This site's markup is unfathomable.

O'Reilly published this recipe as

<pre>def qsort(L):
    if len(L)

</pre>

Add a comment

Sign in to comment

Created by Nathan Gray on Tue, 7 Aug 2001 (PSF)
Python recipes (4583)
Nathan Gray's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks