Three Beautiful Quicksorts
Google engEDU
54 min – Aug 9, 2007

Google Tech Talks
August 9, 2007

ABSTRACT

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.)
video
http://video.google.com/videoplay?docid=-1031789501179533828

• Download: “Three Beautiful Quicksorts” (video/mp4)

Related posts

• 15 Views Of A Node Link Graph: An Information Visualization Portfolio (0)
• 235 Infinity (0)
• 7 Habits For Effective Text Editing 20 (0)
• 7 Ways To Ruin A Technological Revolution (0)
• A Googly Mysql Cluster Talk (0)