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…

Ian Bicking commented on Fri Dec 15 13:18:50 2006:

Isn’t “def q(s):” shorter than “q=lambda a:” ?

Paul commented on Fri Dec 15 15:43:24 2006:

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

Mark Byers commented on Fri Dec 22 12:03:03 2006:

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)

Mark Byers commented on Fri Dec 22 12:06:08 2006:

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)

Mark Byers commented on Fri Dec 22 12:11:35 2006:

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)

Antti Rasinen commented on Sat Dec 23 02:28:33 2006:

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.

Paul commented on Sat Dec 23 11:03:22 2006:

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!

Adal Chiriliuc commented on Fri Jan 5 04:23:09 2007:

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]])

nmessenger commented on Sat Feb 3 03:39:11 2007:

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]

Paul commented on Sat Feb 3 10:16:26 2007:

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.)

LucasBrown commented :

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.