Quick links

Three Beautiful Quicksorts

Date and Time
Wednesday, October 17, 2007 - 4:15pm to 5:45pm
Computer Science Small Auditorium (Room 105)
Jon Bentley, from Avaya Labs Research
Brian Kernighan
This talk describes three of the most beautiful pieces of code that I have ever written: three different implementations of Hoare?s classic Quicksort algorithm. The first implementation is a bare-bones function in about a dozen lines of C. The second implementation starts by instrumenting the first program to measure its run time; a dozen systematic code transformations proceed to make it more and more powerful yet more and more simple, until it finally disappears in a puff of mathematical smoke. It therefore becomes the most beautiful program I never wrote. The third program is an industrial-strength C library Qsort function that I built with Doug McIlroy. A theme running through all three implementations is the power of elegance and simplicity. (This talk expands my Chapter 3 in Beautiful Code, edited by Oram and Wilson and published by O?Reilly in July, 2007.)
Follow us: Facebook Twitter Linkedin