E-Scribe News : a programmer’s blog

About Me

PBX I'm Paul Bissex, and e-scribe.com is my consulting business. I build web applications using open source software, especially Django. In the '90s I did graphic design for newspapers and magazines. Then I wrote technology commentary and reviews for Wired, Salon.com, Chicago Tribune, and lots of little places you've never heard of. Feel free to email me.

Book

I'm co-author of "Python Web Development with Django", an excellent guide to my favorite web framework. Published by Addison-Wesley, it is available from Amazon and your favorite technical bookstore as well.

Colophon

Built using Django, served by Apache and mod_wsgi. The database is SQLite. The operating system is FreeBSD, on a VPS hosted at Johncompanies.com. Comment-spam protection by Akismet. Vintage topo imagery from the Maptech archive. The markup engine is Markdown.

Pile o'Tags

ajax apple blogs browsers business design django ebay fp fun google hardware haskell intellectual property iphone javascript linux media mercurial mobile open source os x oscon oscon2007 palm php programming python rails rants reading risks ruby site spam textmate the well tips tools unix vcs web development web frameworks webservers wmassdevs writing

Stuff I Use

Akismet, bitbucket, del.icio.us, Django, Emacs, FreeBSD, Git, jQuery, LaunchBar, Markdown, Mercurial, OS X, Postfix, Python, Review Board, S3, SQLite, TextMate, Ubuntu Linux

Spam Report

At least 95844 pieces of comment spam killed since January 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

Some related posts: The Language I Will Kind of Learn in 2008: Smalltalk • Neat Python hack: infix operators • "Reverse" game update -- my language safari • Let's play a game: BASIC vs. Ruby vs. Python vs. PHP • Ajaxy regex tester in Python: retest • Evolving a new keyboard • Figlet Captcha • BASIC Computer Games • A Ruby happening • CodeZoo
• 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&lt;s[0]])+[s[0]]+q([x for x in s[1:]if x&gt;=s[0]])

e='q([x for x in s[1:]if x';q=lambda s:s and eval(e+'&lt;s[0]])+[s[0]]+%s&gt;=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+'&gt;x])+[s[0]]+%s&lt;=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.)

[codegolf]: http://codegolf.com/

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

Post a comment

Thanks for reading! Please note: Your comment will not appear until approved, which may take a few hours or more. Spammers will be torpedoed.


(Will not be shared)

(Optional)