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.
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 ] ) + \ [ L ] + qsort( [ ge for ge in L[1:] if ge >= L ] ) # 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.