Click here to Skip to main content
Click here to Skip to main content
Go to top

A QuickSort Algorithm With Customizable Swapping

, 19 Jan 2004
Rate this:
Please Sign up or sign in to vote.
Ever need to customize the swapping function when sorting? This class lets you do that.

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 The 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 <BR>// 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, <BR>                             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 <BR>// 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, <BR>                   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! 

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

Share

About the Author

Marc Clifton

United States United States
Marc is the creator of two open source projets, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.
 
Marc lives in Philmont, NY.

Comments and Discussions

 
GeneralOther algorithm.... PinmemberSuper Lloyd2-May-07 20:22 
GeneralGetting the Rank PinmemberMichael Moreno23-Jan-06 23:07 
GeneralComplexity PinmemberRobert van Poelgeest24-Jan-04 7:03 
GeneralRe: Complexity PinmemberTreBorg20033-Feb-04 5:25 
GeneralIList PinmemberJonathan de Halleux24-Jan-04 6:49 
GeneralRe: IList PineditorMarc Clifton24-Jan-04 6:55 
GeneralRe: IList PinmemberJonathan de Halleux24-Jan-04 9:48 
GeneralRe: IList PinmemberRobert van Poelgeest26-Jan-04 3:05 
GeneralRe: IList PinmemberJonathan de Halleux26-Jan-04 6:27 
GeneralRe: IList PinmemberRobert van Poelgeest27-Jan-04 0:04 
GeneralRe: IList PinmemberJonathan de Halleux25-Jan-04 7:25 
GeneralRe: IList PineditorMarc Clifton25-Jan-04 8:03 
GeneralRe: IList PinmemberJonathan de Halleux25-Jan-04 8:39 
GeneralQuisort -&gt; non static PinmemberJonathan de Halleux24-Jan-04 6:49 
GeneralDelegates PinmemberChristopher Lord21-Jan-04 18:34 
GeneralRe: Delegates PineditorMarc Clifton23-Jan-04 4:06 
GeneralNice PinmemberJonathan de Halleux20-Jan-04 9:02 
GeneralRe: Nice PineditorMarc Clifton20-Jan-04 10:50 
GeneralRe: Nice PinmemberJonathan de Halleux20-Jan-04 22:35 
GeneralRe: Nice PineditorMarc Clifton21-Jan-04 4:32 
GeneralRe: Nice PinmemberTreBorg20032-Feb-04 18:43 
GeneralRe: Nice PineditorMarc Clifton3-Feb-04 1:29 
GeneralRe: Nice PineditorMarc Clifton3-Feb-04 1:43 
GeneralRe: Nice Pinmemberabcdefgqwerty3-Jan-07 6:42 
GeneralRe: Nice PinprotectorMarc Clifton3-Jan-07 7:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140922.1 | Last Updated 20 Jan 2004
Article Copyright 2004 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid