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.

Enjoyed this post? Why not sign up to receive Status-Q in your inbox?

Got Something To Say:

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

*

© Copyright Quentin Stafford-Fraser