The quicksort routine does all the work and, of course it is recursive:

void quicksort(int start, 
        int finish, ref int[] data)
{
 if (start >= finish) return;
 int L=start;
 int R=finish;
 int pivot = data[
     start + (finish - start) / 2];
 scan(ref L,ref R,pivot,data);
 while(L!=R)
 {
  swap(ref data[L], ref data[R]);
  if(data[L]==pivot && 
              data[R]==pivot)L++;
  scan(ref L,ref R,pivot,data);
 }
 quicksort(start,L-1,ref data);
 quicksort(R+1,finish,ref data);
}

You can see that, as explained in the discription of the algorithm, what happens is that the pivot is selected as the middle value and then a scan and swap operation is repeatedly performed.

When the pointers meet the loop ends and there is no need to perform a swap. The final If statement in the loop checks to see if the L and R pointers are both stuck on a pivot and if so moves the L pointer on by one.

Finally the recursive calls to the quicksort sort the left and right portions of the array. Notice that as the calls use “start to L-1” and “R+1 to finish” the recursive calls are guaranteed to finish because the array always grows shorter by at least one and it is assumed that it contains the pivot value.

Finally we need the scan routine –

void scan(ref int L, 
 ref int R,int pivot,int[] data)
 {
 while (data[L] < pivot)
 {
  L++;
  if (L == R) return;
 }
 while (data[R] > pivot)
 {
  R--;
  if (L == R) return;
 }
}

I have to admit that this routine does make rather brutal use of return to terminate it without having to “unwind” the control structures. Many programmers would consider jumping straight out of a loop and on out of the procedure to be bad taste.

After thinking about it for some time I think that it is the best way to express the idea that the condition L=R really is terminal and there is nothing more to do!

All we need to complete the program are some trivial utility routines the swap routine:

void swap(ref int a, ref int b)
{
 int t = b;
 b = a;
 a = t;
}

And the print data routine:

void printdata(int[] data)
{
 for (int i = 0; i < n; i++)
 {
  Console.WriteLine(data[i].ToString());
 }
}

Now you can try it all out.

It works and it works with repeated values, repeated pivots, all values identical and it works if the array is already sorted. It does work fast but notice that for small and special forms of data other sort routines can be faster – QuickSort shows its worth when you have lots of data to be put into order.

You can even make QS faster by using an alternative sorting method when the size of the sub array reaches a set size. You can tinker with it to improve its performance to your heart’s content – clearly if you really are after speed then you should implement it in a more efficient language such as C/C++ or better use a tried and tested routine rather than creating your own.

What is really surprising is how sensitive the QS algorithm is to the exact implementation. What appear to be very small changes in the algorithm, or in the assumptions about the data, produce something that doesn’t work in a big way!

To access the code for this project, once you have registered,  click on CodeBin.

<ASIN:076375756X>

<ASIN:0201118890>

<ASIN:0201485419>

<ASIN:0763707821>