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.
Download
Copy to clipboard1 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.
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:
ASPN, you may want to fix this problem, since line continuations are common in python. (Be aware that the "\" shows up in the preview).
Sigh. Yes, the "\" was dropped again from the above comment. I give up. :-(
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.
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.
Just For Fun: Quicksort in 1 Line. Of course this must not be used in real code too!
This lambda expression is just a rewriting of this function:
Bug in quicksort long form...
Running q(eq) will infinitely recurse. Use eq instead of q(eq)
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:
</pre>
Correction. This site's markup is unfathomable.
O'Reilly published this recipe as
</pre>