Visual C# 2005 Guide
QuickSort

The quicksort is a beast. It was invented by C Hoare (I'm not making these names up) and works by splitting the list into ever smaller sublists which are easier to sort. The algorithm is fairly long and requires a bunch of procedures and functions.

If you have patiently messed around with each of the sorting algorithms on the site, you may have worked out that the Array class already has a sort method. That sort method uses a version of the quicksort algorithm which has deservedly gained a reputation for being one of the quickest ways to sort data.

QuickSort Procedures

static void QSort()
{
   RecQSort(0, randomArray.GetLength(0) - 1);
}

static void RecQSort(int first, int last)
{
   if ((last - first) <= 0)
   {
      return;
   }
   else
   {
      int part = Partition(first, last);
      RecQSort(first, part - 1);
      RecQSort(part + 1, last);
   }
}

static int Partition(int first, int last)
{
   double pivotVal = randomArray[first];
   int thefirst = first;
   bool okSide = true;
   first += 1;
   do
   {
      okSide = true;
      while (okSide)
      {
         if (randomArray[first] > pivotVal)
         {
            okSide = false;
         }
         else
         {
            first += 1;
            okSide = (first <= last);
         }
      }
      okSide = (first <= last);
      while (okSide)
      {
         if (randomArray[last] <= pivotVal)
         {
            okSide = false;
         }
         else
         {
            last -= 1;
            okSide = (first <= last);
         }
      }
      if (first < last)
      {
         Swap(first, last);
         first += 1;
         last -= 1;
      }
   }
   while (first <= last);
   Swap(thefirst, last);
   return last;
}

static void Swap(int item1, int item2)
{
   double temp = randomArray[item1];
   randomArray[item1] = randomArray[item2];
   randomArray[item2] = temp;
}

Having A Go

  1. Using all of the sorting algorithms on this site, adapt your sorting program to run all of the algorithms on the same random set of data. Compare the performance of each list with 100, 1000, 10000, 100000, 1000000 items. Once the computer hangs for too long on the basic algorithms, just run the shell and quicksort.