Quicksort

Paul Bissex has a lovely example of the power of Python – a Quicksort implementation in 99 bytes.

>>> q=lambda s:s if len(s)<2 else q([x for x in s[1:]if x<s [0]])+[s[0]]+q([x for x in s[1:]if x>=s[0]])
>>> print q([9,7,5,3,1,8,6,4,2])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>

If you unwrap it to make it a bit more readable, it’s doing this:

q=lambda s:
   s if len(s)<2 
   else 
      q( [ x for x in s[1:] if x<s[0] ] )
     +[ s[0] ]
     +q( [ x for x in s[1:] if x>=s[0] ] )

Very nice! Needs Python 2.5. If you don’t know the Quicksort algorithm, here’s how it works.

Leave a Reply

© Copyright Quentin Stafford-Fraser