Three Beautiful QuicksortsHave 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);

int main() {
    int i;
    quicksort(0, S(x)-1);
    for (i = 0; i < S(x); i++) {
        printf("%d ", x[i]);
    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.

hacker news, ycombinator logoHere is something neat that I hacked together - a `top' like Python program (called Hacker Top) to follow the Hacker News from the console!

Hacker News has become the 2nd source for news after programming.reddit for me. I have a couple of ideas for a startup myself and the tips I get from Hacker News are priceless.

If you have never heard of Hacker News, I suggest you visit the site ( It's a Digg/Reddit like social news site for startup founders and hackers created by Paul Graham.

This program works ideally for me. I spend lots of hours hacking away at my shell and all I have to do is switch the terminals to the one running the Hacker Top program to get the latest stories!

Here is a screenshot of the program running:

hacker top, detailed mode
Try the 'm' keyboard shortcut to change display modes!


Download link: hacker top program
Downloaded: 5889 times

Note - this program is released under GNU GPL.

How to run the program?

1) Make sure you are running a Unix type operating system.

2) Make sure you have Python installed. Any recent version will do.

3) Download and unpack the hacker top program archive.

$ wget ''
$ tar -xvzf hacker-top.tgz

4) Change to 'hacker-top' directory which was created by unpacking the archive.

$ cd hacker-top

5) Give the '' program execute permissions.

$ chmod u+x

6) Run the program.

$ ./

(If that does not work out, try running 'python ./')

Also make sure your terminal is at least 80 columns wide, otherwise the program won't be able to display the results nicely.

Command Line Options

If you run the program with '--help' argument, it will display the possible command line options:

Usage: ./ [-h|--help] - displays this
Usage: ./ [-i|--interval interval]
          [-u|--utf8 <on|off>] [-n|--new]

As the help message suggests, the three main options are:

  • -i or --interval, which specifies refresh interval.

    The default refresh interval is 3 minutes. Here are a few examples: 10s (10 seconds), 12m (12 minutes), 2h (2 hours).

  • -u or --utf8, turns on utf8 output mode.

    Default: off. Use this if you know for sure that your terminal supports it, otherwise you might get gibberish.

  • -n or --new, which follows only the newest hacker stories.

    Default: follow front page stories.

Keyboard Shortcuts

There are several keyboard shortcuts which you should know about when using the Hacker Top program:

  • q - quits the program.
  • u - forces an update of the news.
  • up arrow/down arrow (or alternatively j/k keys) - scrolls the news list up or down.
  • m - changes the display mode. There are 5 different display modes for your taste.

Enjoy the program! I'll write some details how I created it in one of the next posts. Stay tuned - subscribe to my rss feed! :)

Download Hacker Top Program

Download link: hacker top program
Downloaded: 5889 times

The program is released under GNU General Public License.

ps. Be sure to read Hacker News Guidelines and FAQ if you decide to join the hacker community and star submitting interesting hacker news.

graduate hatI just graduated with a Bachelor of Science degree in Physics from the University of Latvia!

It took me 4 years to complete the studies. During these years I took more than 50 courses from physics, mathematics and computer science departments and my average grade was 9.1/10 (students in Latvia are graded from 1 up to 10, 10 being excellent, 9 being very good, ..., 4 being the lowest grade for passing a course. Anything below 4 means failure).

As I already mentioned in the about me page, I chose to study physics because I already had a broad understanding of various topics of computer science. Now I can proudly say that I understand a lot of physics as well.

Here is a picture of me with a diploma in my hands. :)

peteris krumins with a diploma at university of latvia

Here is another picture with all of us who graduated from University of Latvia with a B.Sc. degree in Physics in 2008. I'm right in the middle of the front row!

university of latvia physics graduates 2008

Talking about my future plans, I decided not to go to a graduate school just yet. I'll spend the next year or two hacking on whatever interests me the most and learn exactly what I have wanted (more mathematics and more computer science). It also means that I will be able to post more frequently here. :)

Thanks for reading my blog!

This article is part of the article series "Musical Geek Friday."
<- previous article next article ->

richard stallman - gnu free software foundation - the free software songThis week on Musical Geek Friday - The Free Software Song!

The song is written and performed by the founder of Free Software Foundation and the most active free software advocate Richard Stallman (scroll down for a video of Mr. Stallman performing it himself).

Richard wrote this song at a filksinging session at a science fiction convention. He realized he had never written a filksong relating to free software, so he figured it was time he did. He remembered that he had never written a filksong using Bulgarian dance music, so he figured that would be a good thing to do for once. He chose Sadi Moma because it is not too fast or complicated, and is easy to sing.

Here it is - The Free Software Song!


Download this song: the free software song.mp3 (musical geek friday #9)
Downloaded: 14449 times

Download lyrics: the free software song lyrics (musical geek friday #9)
Downloaded: 1921 times

Here is the lyrics of The Free Software Song:

Join us now and share the software;
You'll be free, hackers, you'll be free.
Join us now and share the software;
You'll be free, hackers, you'll be free.

Hoarders may get piles of money,
That is true, hackers, that is true.
But they cannot help their neighbors;
That's not good, hackers, that's not good.

When we have enough free software
At our call, hackers, at our call,
We'll throw out those dirty licenses
Ever more, hackers, ever more.

Join us now and share the software;
You'll be free, hackers, you'll be free.
Join us now and share the software;
You'll be free, hackers, you'll be free.

Here is Richard Stallman himself performing The Free Software Song:

The audio quality of this video is poor. Here is a much better version by a band with a hilarious title "The GNU/Stallmans":

Download "The Free Software Song"

Download this song: the free software song.mp3 (musical geek friday #9)
Downloaded: 14449 times

Download lyrics: the free software song lyrics (musical geek friday #9)
Downloaded: 1921 times

Click to listen:

Have fun and until next geeky Friday! :)

shmoocon hacker hacking videosHere are more hacker videos (previous post was on Defcon videos). This time they are from Shmoocon hacker conference. They put out videos from 2006, 2007 and they are putting out videos from 2008 pretty soon.

Shmoocon, as they describe themselves, is an annual East coast hacker convention hell-bent on offering three days of an interesting atmosphere for demonstrating technology exploitation, inventive software & hardware solutions, and open discussions of critical infosec issues.

Here are the videos from Shmoocon 2006:

Here are the videos from Shmoocon 2007:

Here are the videos from Shmoocon 2008:

Enjoy and don't forget to comment on which videos you liked the best!