A QuickSort Algorithm With Customizable Swapping

• Download source files - 1 KB

Introduction

I recently needed to order the rows in a matrix based on the value of the data in a particular column. This wasn't coming from a database, so a nice "order by" SQL clause wouldn't work. I also wasn't using a DataTable and its associated DataView class, so the Sort property wasn't an option either--I was using my own Matrix class. My first thought was, this is easy, I'll just specify my own IComparer when I call the Sort method for the column ArrayList and look up the interface that lets me swap the items. It's probably called ISwap!

NOT! There is no ISwap or similar interface. There is no way to override the swapping of elements in an array! Even worse, as I started digging around to things manually, there isn't even a sort algorithm provided, like good 'ol qsort!

Two Steps Backwards for One Step Forward

The first thing to do was to find a quicksort algorithm. I stumbled across two, but one was only available cached on Google. The other is from the MSDN academic alliance: http://www.msdnaa.net/Resources/Display.aspx?ResID=952. (No, I didn't find a C# implementation on Code Project). The drawback with this algorithm is that it's built around comparing an array of strings, doesn't support an external comparer, and certainly doesn't support an external swapper.

The ISwap Interface

So, first I created the ISwap interface:

// my own interface, allowing control over the swap process
public interface ISwap
{
  void Swap(ArrayList array, int left, int right);
}

The QuickSort Implementation

Then I heavily modified the code in the above link to work with objects, not strings, and to allow the application to specify an IComparer as well. For ease of use, a built in string-based comparitor and built-in swapper is provided. The static constructors allow for a variety of usage syntaxes:

// The basic constructor does a quicksort using the built in comparer 
// and swapper
public static void QuickSort(ArrayList array)
{
  Sort s=new Sort();
  Sort.comparer=s;
  Sort.swapper=s;
  QuickSort(array, 0, array.Count-1);
}

// Specifies my own swapper, but the default comparer
public static void QuickSort(ArrayList array, ISwap swapper)
{
  Sort.comparer=new Sort();
  Sort.swapper=swapper;
  QuickSort(array, 0, array.Count-1);
}

// Specifies my own comparer, but the default swapper
public static void QuickSort(ArrayList array, IComparer comparer)
{
  Sort.comparer=comparer;
  Sort.swapper=new Sort();
  QuickSort(array, 0, array.Count-1);
}

// Specifies both my comparer and my swapper
public static void QuickSort(ArrayList array, IComparer comparer, 
                             ISwap swapper)
{
  Sort.comparer=comparer;
  Sort.swapper=swapper;
  QuickSort(array, 0, array.Count-1);
}

The implementation is the basic quicksort which you can read more about here (one of the numerous descriptions you can find on the Internet). The only salient part of the code is where the comparitor and the swapper are called, which is in the Pivot method:

private static int Pivot(ArrayList array, int lower, int upper)
{
  // Pivot with first element
  int left=lower+1;
  object pivot=array[lower];
  int right=upper;

  // Partition array elements
  while (left <= right)
  {
    // Find item out of place
    while ( (left <= right) && (comparer.Compare(array[left], pivot) <= 0) )
    {
      ++left;
    }

    while ( (left <= right) && (comparer.Compare(array[right], pivot) > 0) )
    {
      --right;
    }

    // Swap values if necessary
    if (left < right)
    {
      swapper.Swap(array, left, right);
      ++left;
      --right;
    }
  }

  // Move pivot element
  swapper.Swap(array, lower, right);
  return right;
}

Usage

Using the algorithm is very simple. For example, in my Matrix class, which manages a collection of columns where each column element is a collection of rows, I provide a method to sort the rows based on a numeric value in a column:

// sort the cells in the specified column in numeric order.
// if the cell in the column needs to be moved, then all other cells in the 
// other columns need to be moved also
public void SortNumeric(int col)
{
    // sort the rows in the specified column
    Sort.QuickSort(((ColumnList)columnList[col]).Rows, 
                   new NumericComparer(), this);
}

A sealed class implements the numeric comparer:

sealed class NumericComparer: IComparer
{
  public int Compare(object x, object y)
  {
    return Convert.ToInt32(((Cell)x).Val) - Convert.ToInt32(((Cell)y).Val);
  }
}

And the matrix implements the ISwap method:

public void Swap(ArrayList array, int left, int right)
{
  foreach (ColumnList col in columnList)
  {
    string obj=col[right];
    col[right]=col[left];
    col[left]=obj;
  }
}

This method ignores the array passed into the method because it actually needs to swap all the elements in the two rows. (And yes, the astute observer will note that my matrix class manages strings. I probably should do something about that some point soon!)

Conclusion

I think the most interesting thing about this was the journey itself. I can understand, for performance reasons, that a sort algorithm usually doesn't want to make the swap function definable outside of itself, but that doesn't totally fly with me because of course the comparison function can be defined for one's specific needs. I was also amazed at the dearth of quicksort examples in C#, and that no one had done this before. Certainly, getting what I wanted done was like taking two steps backwards for one step forward! Well, here may be the solution that you are looking for!

History

• 20^th January, 2004: Initial version

License

This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.

A list of licenses authors might use can be found here.