E-Scribe : a programmer’s blog

About Me

PBX I'm Paul Bissex. I build web applications using open source software, especially Django. Started my career doing graphic design for newspapers and magazines in the '90s. Then wrote tech commentary and reviews for Wired, Salon, Chicago Tribune, and others you never heard of. Then I built operations software at a photography school. Then I helped big media serve 40 million pages a day. Then I worked on a translation services API doing millions of dollars of business. Now I'm building the core platform of a global startup accelerator. Feel free to email me.

Book

I co-wrote "Python Web Development with Django". It was the first book to cover the long-awaited Django 1.0. Published by Addison-Wesley and still in print!

Colophon

Built using Django, served with gunicorn and nginx. The database is SQLite. Hosted on a FreeBSD VPS at Johncompanies.com. Comment-spam protection by Akismet.

Elsewhere

Pile o'Tags

Stuff I Use

Bitbucket, Debian Linux, Django, Emacs, FreeBSD, Git, jQuery, LaunchBar, macOS, Markdown, Mercurial, Python, S3, SQLite, Sublime Text, xmonad

Spam Report

At least 236610 pieces of comment spam killed since 2008, mostly via Akismet.

99-byte Python quicksort

Update: Browsing through my Python Cookbook this evening I discovered entry 5.11, "Showing off quicksort in Three Lines", which includes some code very much like mine below. The entry does a good job of emphasizing that these bits of code are perhaps to be savored but not to be actually used. It also includes an insanely (impressively?) convoluted version that uses three lambdas in a single line and weighs in at 105 bytes. I thought this might be the best possible in Python 2.4 and earlier, but in fact a simpler version can be constructed using the old short-circuit logic trick, and at 94 bytes it's even smaller than my original. Here it is: q=lambda s:len(s)and q([x for x in s[1:]if x<s[0]])+[s[0]]+q([x for x in s[1:]if x>=s[0]])or s

Enticed by the lovely Haskell quicksort example, and sullied by the code-crunching ways of Codegolf, I decided to see how small a Python quicksort function I could write. I stopped at 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 that's hard to read, try the colorized version.)

This requires Python 2.5 because of its use of the new ternary x-if-y-else-z syntax. Please, no style comments! Unreasonable compression is the whole point. I have to say, though, that in terms of readability Python holds up better than most languages under this kind of treatment. Not so much in this example, though...

Friday, December 15th, 2006
+ +
11 comments

Comment from Ian Bicking , later that day

Isn't "def q(s):" shorter than "q=lambda a:" ?

Comment from Paul , later that day

Yes, but with a def you also need a return.

Comment from Mark Byers , 1 week later

Here is a slightly shorter program at 86 bytes:

q=lambda s:s and q([x for x in s[1:]if x=s[0]])

And even shorter, at 82 bytes:

e='q([x for x in s[1:]if x';q=lambda s:s and eval(e+'=s[0]])'%e)

Comment from Mark Byers , 1 week later

Let's try that again:

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

e='q([x for x in s[1:]if x';q=lambda s:s and eval(e+'<s[0]])+[s[0]]+%s>=s[0]])'%e)

Comment from Mark Byers , 1 week later

Slightly rearranging gets a 79 byte version:

e='q([x for x in s[1:]if s[0]';q=lambda s:s and eval(e+'>x])+[s[0]]+%s<=x])'%e)

Comment from Antti Rasinen , 1 week later

Is this really quicksort in terms of how many opertations this consumes? It seems to me that this version goes through each intermediate list twice, where as the canonical version of quicksort should do it only once. Of course the canonical version also does two operations inside the iteration.

I'd have to go through this with paper and pen, but will Santa approve me writing down pseudocode at the Xmas dinner?

It'd be enlightening to do performance comparisons between this code and the "old way" of doing quicksort, though.

Comment from Paul , 1 week later

I believe the biggest factor that makes this not-a-real-quicksort is that it doesn't sort the items in place. I blame the Haskell guys for starting it!

Comment from Adal Chiriliuc , 2 weeks later

A version which more closely resembles the original:

q=lambda s:[] if s==[] else q([x for x in s[1:]if x=s[0]])

Comment from nmessenger , 7 weeks later

This pretty closely resembles the canonical Haskell quicksort:

sort [] = []
sort (x:xs) = sort (filter (<x) xs) ++ [x] ++ sort (filter (>=x) xs)

And this reduces to a paltry 45 bytes:

q[]=[];q(h:t)=q[x|x<-t,x<h]++h:q[x|x<-t,h<=x]
Comment from Paul , 7 weeks later

An excellent example of why I think it would be interesting to add Haskell to Codegolf!

(I patched up your comment, BTW. Anti-spam measures make posting code a bit harder than it should be.)

Comment from LucasBrown , 3 years later

Prompted by Antti Rasinen's comment, I ran some comparisons. The algorithm in the original post runs about 0.5% faster than a "standard" Python quicksort; the others were buggy and I couldn't figure out how to get them to work.

Comments are closed for this post. But I welcome questions/comments via email or Twitter.