E-Scribe News : a programmer’s blog

About Me

PBX My name is Paul Bissex, and e-scribe.com is my consulting business. I build web applications using as much open source software as possible. From September to June I teach web design and other important non-photographic professional skills to photographers. In the '90s I wrote technology commentary and reviews for magazines, newspapers, and web publications, including Wired, Salon.com, FamilyPC, the late lamented Web Review, and the Chicago Tribune. Feel free to email me.

Book Project

I'm co-authoring a book, "Python Web Development with Django", with Jeff Forcier and Wesley Chun. It will be published by Prentice Hall in July 2008, but is available for pre-ordering on Amazon now.

Colophon

This site is built on a fresh trunk checkout of Django, running on Python 2.5.1, served by Apache and mod_python. 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.

Pile o'Tags

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

Stuff I Use

Akismet, del.icio.us, Django, dpaste.com, Emacs, FreeBSD, Freenode, jQuery, LaunchBar, MacPorts, Markdown, Mercurial, OS X, Postfix, Python, SQLite, Subversion, TextMate, Trac, Ubuntu Linux, wmii

A Django site.
(Finally!)

Copyright 2008
by Paul Bissex
and E-Scribe New Media

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

Post a comment

Comments use Markdown syntax. Your comment will not appear until approved, which may take a few hours or more. Spammers will be torpedoed.


(Will not be shared)

(Optional)