ActiveState Powered by ActiveState

Recipe 66473: Just For Fun: Quicksort in 3 Lines

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 
 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!'

Discussion

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.

Comments

  1. 1. At 1:42 p.m. on 7 aug 2001, Nathan Gray (the author) said:

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

  2. 2. At 1:43 p.m. on 7 aug 2001, Nathan Gray (the author) said:

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

  3. 3. At 2:03 p.m. on 7 aug 2001, Nathan Gray (the author) said:

    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.

  4. 4. At 3:16 a.m. on 28 feb 2002, Raymond Hettinger said:

    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))
  5. 5. At 2:59 p.m. on 25 aug 2002, Christophe Delord said:

    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
  6. 6. At 7:18 p.m. on 15 jan 2003, Jeremy Zucker said:

    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)

  7. 7. At 3 p.m. on 23 jul 2004, Dave Edwards said:

    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>

  8. 8. At 3:02 p.m. on 23 jul 2004, Dave Edwards said:

    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>

Sign in to comment