Quicksort

Choose Your Browser

Home Page
Work
Sample Code


Word Count
Word Count
Word Count
Remove Tab
Anagram
8 Queen
Permute
Nim
Quicksort

I think that all these years, people has been repeating the mantra that quicksort is hard, that they start to believe in it, and never realize how easy it is to do quick sort! Yes, that's right. Quicksort is easy. Of course, it's hard the first time you see it, but I don't think that it should still be hard after a few times you try it. In fact, I find it too easy!

You don't believe me? Try it yourself! The whole function takes only four lines. Five if you include variable declarations. As far as I know, I'm the only who posted quicksort in 4 lines solution. Just type in "quicksort in four lines" and you'll get this page. I decided to put this simple concept to a little test, to see just how many people can actually do it. It's rather disheartening to realize that the odds of success is 1 in 1000. That's one in one thousand! Can you believe it?

Anyway, here's the challenge. Just make the function work by filling in the missing piece and you're there. Here's a couple of hints: The array a[] is global and var p is the pivot point. Another hint: Just use var i as the loop variable.

/* QuickSort demonstration       */
/* Written by Harry M. Hardjono  */
/* Jan 1 2002                    */
/* Assume array of integers a[] */
void quicksort(int lo, int hi) {
  int i,p;

  if (lo>=hi) return;

  /* Fill in the missing line here... */

  quicksort(lo, p-1);
  quicksort(p+1, hi);
}

Henry Wong
  for ((a[i=lo+1]<a[p=lo])?(a[i]^=a[p]^=a[i]^=a[p]):0 ;
        i<hi;
        (a[++i]<a[p])? (a[p++]^=a[p+1]^=a[p]^= a[p+1]^=a[i]^=a[p+1]^=a[i]):0
      ); 

Michael Kaltner
  for(i=hi,p=lo;p<i;)
    if(a[p]>a[p+1]) a[p++]=(a[p]+a[p+1])-(a[p+1]=a[p]);
    else            a[i--]=(a[i]+a[p+1])-(a[p+1]=a[i]);

Paul Bartrum
  for (i=p=lo; i<=hi; i++) if(a[i]<a[p]) swap(p, i), swap(i, ++p);

  and

  #define swap(x, y) (a[x]^=a[y]^=a[x]^=a[y])
  for (i=p=lo; i<=hi; i++)
     if(a[i]<a[p] && swap(p, i)*0==0 && ++p!=i)
       swap(p, i);

I am sad and disappointed that no one actually got the right answer. The problem here is that choosing the first element as the pivot value means that you lose track of it as soon as you swap it. There are two solutions. The first solution is that you skip one step ahead, keeping the pivot element as the first element of the array. This works, except that due to the way the recursive function is called, it's not really one line, but two. The closest one to my algorithm is Da Kong. His algorithm is as follows:

Da Kong
  for(i=p=lo; i<hi;)
     if(a[++i]<a[lo] && i>++p)
       a[p]^=a[i]^=a[p]^=a[i];
  if(p>lo) a[p]^=a[lo]^=a[p]^=a[lo];

The question is, is there a better way to do this? It's not the question of what is the best way to keep track the pivot point, but rather, is there a way to do this WITHOUT keeping track of the pivot point? It turns out there is. Instead of choosing the first element as the pivot point, you choose the last! This way, when the element gets swapped, it gets swapped into place and the work is done. I think it solves neatly two problems: Keeping track of pivot point, and putting it into place at the end of the loop. This is the solution I have. It goes by Loop-Conditional-Swap structure:

Harry Hardjono
  for (p=(i=lo)-1; i<=hi; i++)
    if (a[i]<=a[hi] && i!=++p)
      a[i]^=a[p]^=a[i]^=a[p];

  or this...

  for (p=(i=lo)-1; i<=hi; i++) if (a[i]<=a[hi]) swap_int(i,++p);

I'm not even that picky about that one line requirements. As long as I think you're capable of it, I'll accept your answer. The first requirement is that you know how quicksort works, instead of blindly copying algorithm from somewhere else (some entrants did). Also, make sure that it really is quicksort, not sequential sort in disguise! Once you know and understand how quicksort works, you need to come up with the idea of using the last element. It appears that the only people who is smart enough to understand quicksort, is smart enough to do it while bubbling up, and never dreamed that there is an easier way to do it although I must admit Michael's solution is close enough to mine.

Of course, there is the question about the swap, but the swap isn't as thought provoking as pivot selection. You can always research the swap, or just figure it out. It's not that hard. The process goes like this:

Choose the simplest method, the first element as the pivot. Hmmm... I lost track of it by the first swap. I can either bubble it up, or I can choose another element. Let's choose the last, and make sure to swap it at the end of the loop. Since p is the pivot point, and it needs to be incremented, this means that p needs to be incremented before swapping, so if i=lo, then p=lo-1. To make sure the last swap is done, then i<=hi.

  for (p=(i=lo)-1; i<=hi; i++)

    if (a[i]<=a[hi] && i!=++p)

  void swap_int(int x, int y) {
    int t;
    t = a[y];
    a[y] = a[x];
    a[x] = t;
  }

  x=x^y;
  y=x^y;
  x=x^y;

  x=(y=(x=y^x)^y)^x;

  x=(y=(x^=y)^y)^x;
  x=(y^=(x^=y))^x;
  x^=(y^=(x^=y));
  x^=y^=x^=y;

The quicksort that I have is the simplest quicksort possible, I think. However, it's not the best. There are two things wrong with it. The first fault is that it is slower than bubblesort, at least on sorted or nearly sorted data. What kind of data is nearly sorted data? Plenty. For example, keeping track of item ranking sorted according to volume sold, or GPS satellites, or even nearly finished quicksort, as we shall see later.

There are several different ways to fix this fault. The generally recognized best method is the median-of-three method. There was some discussion about whether or not you should swap the elements as you compare the values. I think you should. Therefore you put this routine before partitioning:

  if (a[lo] > a[hi])        swap_int(lo,hi);
  if (a[lo] > a[(lo+hi)/2]) swap_int(lo,(lo+hi)/2);
  if (a[hi] > a[(lo+hi)/2]) swap_int(hi,(lo+hi)/2);

The second fault is less obvious, but much more dangerous since you can't circumvent it by prepping the array. When the list is composed of many identical elements, then it becomes slower than sequential/selection sort! What kind of data has identical elements? Sorting male/female, Rep/Dem/Ind, or sparse array.

This fault is usually overlooked by people, but it is much more devastating since you can't easily circumvent the fault. Robert Sedgewick mentioned this in his book, but only briefly, so many people missed it. You need to use 2 partition points in sorting, to separate elements that are less than pivot, pivots (may be more than one), and elements greater than pivot. Using my existing code, it is trivial to modify the code to fix this.

void quicksort(int lo, int hi) {
  int i,p;  if (lo >= hi) return;

  for (p=(i=lo)-1; i<hi; i++) if (a[i]<a[hi]) swap_int(i,++p);
  quicksort(lo, p);

  for (i=p+1; i<=hi; i++) if (a[i]<=a[hi]) swap_int(i,++p);
  quicksort(p+1, hi);
}

The simplistic method above uses too many swaps. In order to eliminate these unnecessary swaps, you'd want to partition it low-hi. However, in order to make sure that there's no overrun, you need to do an extra check. When you finally eliminate that extra check, you'll probably end up with something similar to what you see everywhere else. It would be interesting to see if you can really optimize that routine and come up with optimized version. Who knows? Maybe you can come up with an efficient way to set up a three way partition!

Another way to optimize would be to not use quicksort all the way through. The actual limit where we want to stop quicksorting and use another sort must be discovered through trial and error, as it heavily depends upon hardware and sorting algorithm used. In this example, we'll use bubblesort to sort nearly sorted array, so we use this code:

  if (hi-lo < 5) return;

  void qsort(int lo, int hi) {
    RandomizeArray(); // for the whole a[]
    quicksort(lo,hi);
    bubblesort(lo,hi); // or use insertion sort
  }

Of course, if you're in a stack tight environment, then it is prudent to remove recursion. However, I'd rather keep track of recursion depth, and call on Shellsort upon reaching a certain depth. It is almost guaranteed that the number of elements by that depth can be easily handled by shellsort. This you can do easily by using static variable or passing in an extra variable.

Speaking of which, a couple entries submitted sequential sort, otherwise known as selection sort. The algorithm works like this: Find the smallest element in the list, and put it left most. Repeat for the next element, each time shifting one. That is my very first sort routine and I must admit that it is slow. However, a simple enhancement makes it much better. Looking at the partitioned routine, it is trivial to create a sequential sort that put the smallest elements (plural) and put it at the end of the list. Increase pointer, and repeat. That means sorting Male/Female will only take two passes, regardless of how many there are. I believe that this similarity with partitioning process is what confuses people to submit a different sort algorithm for this contest. So close to the solution, yet unattainable for some.

Phew! That's a lot of lines to what amounts to quicksort in four lines.

Grand Prize Winner:
Henry Wong < henry@stuffedcow.wox.org >

Honorary Winner List:
Michael Kaltner < mike@mkaltner.com >
Paul Bartrum < paulbartrum@mail.com >
Eric Schneider < mr_sonicblue@mac.com >
R. Eranki < rajiv@macnn.com >
Da Kong < dkong@andrew.cmu.edu >