C# Quicksort

December 10, 2007 – 8:43 pm

Here is a simple implementation of the Quicksort sorting algorithm in C#. This class uses generics so any type that implements IComparable can be sorted. This code is neither intended to be the most efficient Quicksort implementation, nor does it implement Median-of-Three and Insertion sort enhancements; it does, however, provide an easy-to-follow simple implementation of the algorithm. This will provide a solid foundation for the Introsort algorithm that will be presented later. Also, this method is a member of the Sorting class that I will present later, and the generic class T is defined in this context as any class that implements IComparable.

   1:  public void Quicksort (T[] array, int left, int right)

   2:  {

   3:    if (left >= right)

   4:    {

   5:      // done sorting

   6:      return;

   7:    }

   8:    else if (left == right - 1)

   9:    {

  10:      // two element list

  11:      if (array[left].CompareTo(array[right]) > 0)

  12:      {

  13:        // left is greater than the right — swap them

  14:        Swap(array, left, right);

  15:      }

  16:   

  17:      // done sorting

  18:      return;

  19:    }

  20:   

  21:    // since this method is recursive avoid placing these variables on the

  22:    //   stack until the last moment

  23:    int i = left;

  24:    int k = right;

  25:   

  26:    // choose a pivot and move it to the end of the list

  27:    int pivotIndex = (left + right) >> 1; // (left + right) / 2

  28:    T pivot = array[pivotIndex];

  29:    array[pivotIndex] = array[right];

  30:    array[right] = pivot;

  31:   

  32:    while (i < k)

  33:    {

  34:      // move the i index to the k until something is found that is

  35:      //  greater than the pivot

  36:      while ((array[i].CompareTo(pivot) <= 0) && (i < k))

  37:      {

  38:        i++;

  39:      }

  40:   

  41:      // move the k index to the i until something is found that is

  42:      //  less than the pivot

  43:      while ((pivot.CompareTo(array[k]) <= 0) && (i < k))

  44:      {

  45:        k–;

  46:      }

  47:   

  48:      if (i < k)

  49:      {

  50:        // swap i and k

  51:        Swap(array, i, k);

  52:      }

  53:    }

  54:   

  55:    // put the pivot back

  56:    array[right] = array[k];

  57:    array[k] = pivot;

  58:   

  59:    // sort the left side

  60:    Quicksort(array, left, i - 1);

  61:  

  62:    // sort the right side

  63:    Quicksort(array, k + 1, right);

  64:  }

  65:   

  66:  private void Swap (T[] array, int i, int k)

  67:  {

  68:    T swap = array[i];

  69:    array[i] = array[k];

  70:    array[k] = swap;

  71:  }