Three Beautiful Quicksorts

Channel:

Google TechTalks

Subscribers:

349,000

Published on October 9, 2007 3:40:54 AM ● Video Link: https://www.youtube.com/watch?v=aMnn0Jq0J-E

Duration: 53:56

44,350 views

206

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