Three Beautiful Quicksorts

Have you heard about a book called Beautiful Code? This book is composed of 33 essays by well-known computer scientists and software engineers on the same question - "What is the most beautiful piece of code you know?".

Chapter 3 of this book is written by Jon Bentley. The chapter is curiously entitled "The Most Beautiful Code I Never Wrote" and it talks about a beautiful implementation and experimental analysis of the most widely used sorting algorithm in the world called Quicksort.

Jon also decided to give a talk at Google on the same topic. In this techtalk, he talks about three Quicksort topics. In the first part Jon discusses an elegant and tiny implementation of Quicksort. In the next part he analyzes the Quick sort algorithm by instrumenting this elegant implementation. Finally, he talks about a production quality Quicksort implementation which has been included in C standard library (qsort function).

What I learned the most from this lecture is the experimental part of counting number of comparsions of an algorithm. I had never read about experimental analysis of algorithms.

Interesting ideas from the lecture:

  • [02:30] What's the most beautiful code you've ever written?
  • [04:58] The classical Quicksort algorithm.
  • [05:32] Best case (nlog(n)), worst (n2) and average case (nlog(n)) analysis results of Quicksort.
  • [08:00] Randomization in Quicksort.
  • [09:08] Lomuto's idea of partitioning.
  • [10:48] Partitioning algorithm implementation pseudocode.
  • [11:10] Beautiful Quicksort code.
  • [12:13] Strengths of Quicksort: simple to implement and explain, pretty fast. Weaknesses of Quicksort: quadratic time for increasing elements (fix by randomization), quadratic time for equal elements, not stable.
  • [13:55] "vigorous writing is concise" /William Strunk Jr.'s/
  • [14:49] Simplest semi-production C Quicksort implementation.
  • [15:35] How much time will Quicksort take on average on indistinct elements?
  • [17:00] Graph of (runtime/N, logN) for Quicksort and Heapsort.
  • [18:31-32:00] Finding number of comparisons for Quicksort experimentally.
  • [23:08] Doing various tricks the time to count comparisons reduced from nlog(n) to n and space reduced from n to log(n).
  • [24:25] The Inventor's Paradox: "The more ambitious plan may have more chance of success."
  • [30:13] Perlis: "Simplicity does not precede complexity, but follows it."
  • [30:45] Mathematical solution to Quicksort's comparison complexity.
  • [31:35] The solution is ~ 1.386nlog(n)
  • [32:10] Analysis of comparisons in Quicksort is isomorphic to time taken to insert an element in a Binary Search Tree.
  • [36:25] A beautiful bug report on the original implementation of C library's qsort
  • [39:31] Engineering qsort together with Doug McIlroy. Goals and strategy.
  • [41:23] With equal elements, some Quicksorts go quadratic, some go nlog(n), some go linear.
  • [41:46] Is there a quick algorithm for ternary (<, = , >) partitioning?
  • [46:00] Knuth said that the overheard and comparisons took the same amount of time but the swaps really killed you, where as Jon and Doug found that time(overhead) < time(swaps) < time(comparisons), if swaps are done properly.
  • [46:30] Choosing effective partitioning element was important. First, middle or random gave runtime aproximately 1.386nlog(n), where as median of three or median and three medians gave run times of 1.188nlog(n) and 1.09nlog(n), respectivey.
  • [46:50] The final qsort had ternary partitioning, fast swap, adaptive sample for partition element, insertion sort for small files.
  • [47:40] The complete code of C library's qsort.
  • [48:15] Beauties of qsort (beautiful algorithm, beautiful interface, beautiful bug report, beautiful cost models, beautiful tests)
  • [50:40] Three beautiful Quicksorts - 1) a simple teaching tool, 2) an anaysis of Quicksort, 3) An industrial-strength Quicksort.
  • [51:35] Q and A.

Here is a working C program which runs Quicksort algorithm (in bold) from the Chapter 3 of the book. The algorithm sorts the global array of integers x.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define S(a) (sizeof(a)/sizeof(a[0]))

int x[] = { 56, 10, 39, 15, 20, 62, 14, 39, 77, 17 };

void swap(int i, int j) {
    int t = x[i];
    x[i] = x[j];
    x[j] = t;
}

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

<strong>void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}</strong>

int main() {
    int i;
    srand(time(NULL));
    quicksort(0, S(x)-1);
    for (i = 0; i < S(x); i++) {
        printf("%d ", x[i]);
    }
    printf("\n");
    return 0;
}

In a functional programming language, Quicksort can be written even more elegantly. Check out this Quicksort written in Haskell (thanks to bayareaguy.)

  quicksort (x:xs) = 
      quicksort [ i | i <- xs, i < x ] 
      ++ [x] ++
      quicksort [ i | i <- xs, i >= x ]

  quicksort [] = []

And what's the most beautiful code you've ever written?

Ps. If you got interested, I suggest you get the Beautiful Code book. Jon Bentley carefully explains the ticks used for doing the experimental part of analysis in his chapter.

Comments

July 11, 2008, 02:59

It is beautiful code, but a lot more attention needs to be paid to the production quality version. In particular most beautiful quicksorts take O(n^2) time on a list filled with identical items (see Tim Peters ch. in the Python Cookbook or my article Sorting In Anger.

July 11, 2008, 05:15

The haskell algorithm, while about as elegant as code can get, does not use the ingenius in-place sorting that the C version does. Because of this, it has very different space complexity.

Here is a much more C-like version: http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html

Foo Permalink
July 11, 2008, 06:00

Bah.

    (defun quicksort (l)
      (when l
        (destructuring-bind (x . xs) l
          `(,@(quicksort (remove x xs :test #'))))))
Foo Permalink
July 11, 2008, 06:01

Let's try again, this time with proper HTML.

Bah.

    (defun quicksort (l)
      (when l
        (destructuring-bind (x . xs) l
          `(,@(quicksort (remove x xs :test #'<=))
            ,x
            ,@(quicksort (remove x xs :test #'>))))))
July 11, 2008, 06:11

Foo, can you send me the code to peter@catonmat.net so I can fix it?

Wordpress is doing bad things to the code you're trying to submit.

Dan Permalink
July 11, 2008, 06:46

Hehehe...

Considering the machine code produced, the C version would turn out terribly inefficient. It suffers from:

- Noteable recursion overhead when the problem could easily be iterative.
- Bad, but not yet stupid cache coherency
- Excessive branching

Stop thinking about what "code looks pretty" and start thinking about what will function. Next we'll see programmers getting paid for their artistic merit with ascii art in comments.

GTFO.

July 11, 2008, 18:53

Haskells version can be even more compact:

qs (x:xs) = (qs $ filter (x) xs)

shakey Permalink
August 29, 2008, 04:36

python:

def sort(l):
    return [] if l == [] else sort([t for t in l[1:] if t = l[0]])
bunqiejump Permalink
August 20, 2010, 14:23

perl

sub quicksort{
  my (@l,@m,@r)=();
  map {$_<$_[0]?$l[++$#l]=$_:$_==$_[0]?$m[++$#m]=$_:$r[++$#r]=$_} @_;
  return ($#l>=1?quicksort(@l):@l,@m,$#r>=1?quicksort(@r):@r);
}
November 12, 2010, 04:09

Dyalog APL
qsort ← {1≥⍴⍵:⍵⋄e←⍵[?⍴⍵]⋄ (∇(⍵

<e>

e)/⍵}
(And it can get even more concise...)

November 12, 2010, 04:17

the best way: A⍋ (Picks the best algorithm for you...)

November 12, 2010, 04:39

Whoops. I meant ⍒A

June 04, 2014, 10:57

Ya It's best way

faheen Permalink
June 22, 2014, 04:32

Ramadan Wallpaper
Ramadan Wallpaper HD Download
Ramadan Wallpaper 2014
Ramadan Wallpaper 2014 Download
Ramadan Wallpaper 2014 HD Images
Ramadan Wallpaper 2014 Images
Ramadan Wallpaper quotes
Ramadan wallpaper greetings
Ramadan wallpaper 2014 greetings
Ramadan Wallpaper 2014 quotes
Ramadan Kareem 2014 images
Ramadan Kareem Mubarak Images
Ramadan Kareem Mubarak 2014 images
Ramadan Screen Saver 2014 download
Ramadan Mubarak images
Ramadan images 2014
Ramadan Mubarak greetings
Wish you happy Ramadan 2014
Happy Ramadan Wallpaper 2014
Ramadan wallpaper 2014
Wish you happy Ramadan 2014
ramadan Hd wallpaper 2014
Wish you happy Ramadan wallpaper 2014
Ramadan 2014 images
Ramadan 2014 pictures
wish you happy Ramadan 2014 images
Wish you happy Ramadan 2014 pictures
Happy ramadan 2014 wallpaper
Ramadan Kareem 2014 Wallpaper
Ramadan Mubarak 2014 wallpaper
Wallpaper Ramadan 2014
Ramadan HD wallpaper
Ramadan 2014 HD wallpaper
wish you Ramadan 2014 HD wallpaper
Happy Ramadan HD wallpaper
Happy Ramadan 2014 HD wallpaper
Wish you Ramadan HD wallpaper Download 2014
Ramadan HD wallpaper Download 2014
Ramadan HD wallpaper 2014 Download
Ramadan HD wallpaper 1080p
Ramadan 2014 HD wallpaper 1080p
Best Ramadan 2014 HD wallpaper
Top 10 Ramadan 2014 HD wallpaper
Best Collections Of Ramadan 2014 HD wallpaper
Ramadan 2014 HD wallpaper For Android
Ramadan 2014 best Screensaver download
Ramadan 2014 Screensaver download
screensaver download for mobile Ramadan 2014
Ramadan 2014 HD Screensaver Download
Ramadan 2014 download best screen saver
Screensaver for 2014 ramadan
Ramadan mubarak screensaver download
Ramadan mubarak 2014 best screen saver
Ramadan Kareem Mubarak 2014 best screen saver
Ramadan mubarak 2014 best screen saver
screen saver 2014 download free for android
Ramadan Kareem Mubarak Greetings 2014
Best Collections of Ramadan 2014 Greetings
Best Collections of Ramadan 2014 Greetings
Top Collections of Ramadan 2014 Greetings
Ramadan 2014 Greetings
Ramadan 2014 Greetings Free
Ramadan 2014 Greetings Kareem best
Best Collections of Ramadan 2014 Kareem Greetings
Best Collections of Ramadan 2014 Kareem Greetings
Best Collections of Ramadan 2014 kareem greetings
Top Ramadan 2014 wallpapers
Top Ramadan 2014 pictures
Top ramadan 2014 pictures for pc
Top ramadan 2014 Wallpaper for Android
Ramadan 2014 best softwares
Ramadan 2014 Best Images of Desktop
Ramadan 2014 best pictures for desktop
ramadan 2014 collection of Hd wallpaper
Ramadan 2014 Best collections
Ramadan 2014 top Hd wallpaper
Ramadan 2014 in uk
When Ramadan 2014 in Uk
ramadan 2014 in United Kingdom
When Ramadan 2014 in United States
When ramadan 2014 in America
Ramadan date in uk
Ramadan date in uk
Ramadan facts in united kingdom
Ramadan date in France
Ramadan 2014 in france
Ramadan 2014 date in france
Ramadan 2014 date in Frace country
Happy Ramadan 2014 best wallpaper
Ramadan Wallpaper best collections
Ramadan Kareem Wallpaper collections
wish you happy Ramadan wallpaper 2014
happy Ramadan wallpaper 2014
wish you happy Ramadan Hd wallpaper
Happy Ramadan 2014 HD wallpaper
Hd Ramadan wallpaper 2014
Wallpaper 2014 Hd in Ramadan
Ramadan wallpaper 2014 for Desktop Background
Best Islamic Ramadan wallpaper 2014
Wallpaper 2014 for facebook Cover
Best Wallpaper 2014 Download
Ramadan HD wallpaper 2014 Download
When ramadan in India 2014
Ramadan in India 2014
Ramadan in India 2014
Ramadan Kareem Greetings
Ramadan kareem Mubarak Greetings
Ramadan kareeem 2014 Greetings
Ramadan 2014 kareem Greetings
Ramadan 2014 kareem greetings
Ramadan Kareem Mubarak 2014
Ramadan kareem Mubarak 2014
Ramadan kareem Mubarak 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Kareem greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Ramadan Mubarak Greetings 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Inspirational pictures of ramadan 2014
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Ramadan 2014 Wallpaper and Mubarak pics
Awesome Post Ramadan Wallpaper Ramadan Wallpaper HD Download Ramadan Wallpaper 2014 Ramadan Wallpaper 2014 Download Ramadan Wallpaper 2014 HD Images Ramadan Wallpaper 2014 Images Ramadan Wallpaper quotes Ramadan wallpaper greetings Ramadan wallpaper 2014 greetings Ramadan Wallpaper 2014 quotes Ramadan Kareem 2014 images Ramadan Kareem Mubarak Images Ramadan Kareem Mubarak 2014 images Ramadan Screen Saver 2014 download Ramadan Mubarak images Ramadan images 2014 Ramadan Mubarak greetings Wish you happy Ramadan 2014 Happy Ramadan Wallpaper 2014 Ramadan wallpaper 2014 Wish you happy Ramadan 2014 ramadan Hd wallpaper 2014 Wish you happy Ramadan wallpaper 2014 Ramadan 2014 images Ramadan 2014 pictures wish you happy Ramadan 2014 images Wish you happy Ramadan 2014 pictures Happy ramadan 2014 wallpaper Ramadan Kareem 2014 Wallpaper Ramadan Mubarak 2014 wallpaper Wallpaper Ramadan 2014 Ramadan HD wallpaper Ramadan 2014 HD wallpaper wish you Ramadan 2014 HD wallpaper Happy Ramadan HD wallpaper Happy Ramadan 2014 HD wallpaper Wish you Ramadan HD wallpaper Download 2014 Ramadan HD wallpaper Download 2014 Ramadan HD wallpaper 2014 Download Ramadan HD wallpaper 1080p Ramadan 2014 HD wallpaper 1080p Best Ramadan 2014 HD wallpaper Top 10 Ramadan 2014 HD wallpaper Best Collections Of Ramadan 2014 HD wallpaper Ramadan 2014 HD wallpaper For Android Ramadan 2014 best Screensaver download Ramadan 2014 Screensaver download screensaver download for mobile Ramadan 2014 Ramadan 2014 HD Screensaver Download Ramadan 2014 download best screen saver Screensaver for 2014 ramadan Ramadan mubarak screensaver download Ramadan mubarak 2014 best screen saver Ramadan Kareem Mubarak 2014 best screen saver Ramadan mubarak 2014 best screen saver screen saver 2014 download free for android Ramadan Kareem Mubarak Greetings 2014 Best Collections of Ramadan 2014 Greetings Best Collections of Ramadan 2014 Greetings Top Collections of Ramadan 2014 Greetings Ramadan 2014 Greetings Ramadan 2014 Greetings Free Ramadan 2014 Greetings Kareem best Best Collections of Ramadan 2014 Kareem Greetings Best Collections of Ramadan 2014 Kareem Greetings Best Collections of Ramadan 2014 kareem greetings Top Ramadan 2014 wallpapers Top Ramadan 2014 pictures Top ramadan 2014 pictures for pc Top ramadan 2014 Wallpaper for Android Ramadan 2014 best softwares Ramadan 2014 Best Images of Desktop Ramadan 2014 best pictures for desktop ramadan 2014 collection of Hd wallpaper Ramadan 2014 Best collections Ramadan 2014 top Hd wallpaper Ramadan 2014 in uk When Ramadan 2014 in Uk ramadan 2014 in United Kingdom When Ramadan 2014 in United States When ramadan 2014 in America Ramadan date in uk Ramadan date in uk Ramadan facts in united kingdom Ramadan date in France Ramadan 2014 in france Ramadan 2014 date in france Ramadan 2014 date in Frace country Happy Ramadan 2014 best wallpaper Ramadan Wallpaper best collections Ramadan Kareem Wallpaper collections wish you happy Ramadan wallpaper 2014 happy Ramadan wallpaper 2014 wish you happy Ramadan Hd wallpaper Happy Ramadan 2014 HD wallpaper Hd Ramadan wallpaper 2014 Wallpaper 2014 Hd in Ramadan Ramadan wallpaper 2014 for Desktop Background Best Islamic Ramadan wallpaper 2014 Wallpaper 2014 for facebook Cover Best Wallpaper 2014 Download Ramadan HD wallpaper 2014 Download When ramadan in India 2014 Ramadan in India 2014 Ramadan in India 2014 Ramadan Kareem Greetings Ramadan kareem Mubarak Greetings Ramadan kareeem 2014 Greetings Ramadan 2014 kareem Greetings Ramadan 2014 kareem greetings Ramadan Kareem Mubarak 2014 Ramadan kareem Mubarak 2014 Ramadan kareem Mubarak 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Kareem greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Ramadan Mubarak Greetings 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Inspirational pictures of ramadan 2014 Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics Ramadan 2014 Wallpaper and Mubarak pics oHack Anna University Paper Valuation Anna University result 2014 Thanks for sharing

Neo Parker Permalink
July 23, 2014, 10:49

Awesome post
Eid mubarak sms
Eid mubarak images
thanks

Neo Parker Permalink
July 23, 2014, 10:49

Awesome post
Eid mubarak sms
Eid mubarak images
thanks

Neo Parker Permalink
July 23, 2014, 10:49

Awesome post
Eid mubarak sms
Eid mubarak images
thanks

Neo Parker Permalink
July 23, 2014, 10:49

Awesome post
Eid mubarak sms
Eid mubarak images
thanks

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the first letter of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.

Advertisements