Click here to Skip to main content
12,070,942 members (57,153 online)
Click here to Skip to main content
Add your own
alternative version

Stats

116.1K views
205 downloads
48 bookmarked
Posted

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 
// 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! 

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 projects, 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.

You may also be interested in...

Comments and Discussions

 
GeneralOther algorithm.... Pin
Super Lloyd2-May-07 21:22
memberSuper Lloyd2-May-07 21:22 
GeneralGetting the Rank Pin
Michael Moreno24-Jan-06 0:07
memberMichael Moreno24-Jan-06 0:07 
GeneralComplexity Pin
Robert van Poelgeest24-Jan-04 8:03
memberRobert van Poelgeest24-Jan-04 8:03 
GeneralRe: Complexity Pin
TreBorg20033-Feb-04 6:25
memberTreBorg20033-Feb-04 6:25 
GeneralIList Pin
Jonathan de Halleux24-Jan-04 7:49
memberJonathan de Halleux24-Jan-04 7:49 
GeneralRe: IList Pin
Marc Clifton24-Jan-04 7:55
editorMarc Clifton24-Jan-04 7:55 
GeneralRe: IList Pin
Jonathan de Halleux24-Jan-04 10:48
memberJonathan de Halleux24-Jan-04 10:48 
GeneralRe: IList Pin
Robert van Poelgeest26-Jan-04 4:05
memberRobert van Poelgeest26-Jan-04 4:05 
GeneralRe: IList Pin
Jonathan de Halleux26-Jan-04 7:27
memberJonathan de Halleux26-Jan-04 7:27 
GeneralRe: IList Pin
Robert van Poelgeest27-Jan-04 1:04
memberRobert van Poelgeest27-Jan-04 1:04 
GeneralRe: IList Pin
Jonathan de Halleux25-Jan-04 8:25
memberJonathan de Halleux25-Jan-04 8:25 
GeneralRe: IList Pin
Marc Clifton25-Jan-04 9:03
editorMarc Clifton25-Jan-04 9:03 
GeneralRe: IList Pin
Jonathan de Halleux25-Jan-04 9:39
memberJonathan de Halleux25-Jan-04 9:39 
GeneralQuisort -&gt; non static Pin
Jonathan de Halleux24-Jan-04 7:49
memberJonathan de Halleux24-Jan-04 7:49 
GeneralDelegates Pin
Christopher Lord21-Jan-04 19:34
memberChristopher Lord21-Jan-04 19:34 
GeneralRe: Delegates Pin
Marc Clifton23-Jan-04 5:06
editorMarc Clifton23-Jan-04 5:06 
GeneralNice Pin
Jonathan de Halleux20-Jan-04 10:02
memberJonathan de Halleux20-Jan-04 10:02 
GeneralRe: Nice Pin
Marc Clifton20-Jan-04 11:50
editorMarc Clifton20-Jan-04 11:50 
GeneralRe: Nice Pin
Jonathan de Halleux20-Jan-04 23:35
memberJonathan de Halleux20-Jan-04 23:35 
GeneralRe: Nice Pin
Marc Clifton21-Jan-04 5:32
editorMarc Clifton21-Jan-04 5:32 
GeneralRe: Nice Pin
TreBorg20032-Feb-04 19:43
memberTreBorg20032-Feb-04 19:43 
GeneralRe: Nice Pin
Marc Clifton3-Feb-04 2:29
editorMarc Clifton3-Feb-04 2:29 
GeneralRe: Nice Pin
Marc Clifton3-Feb-04 2:43
editorMarc Clifton3-Feb-04 2:43 
GeneralRe: Nice Pin
abcdefgqwerty3-Jan-07 7:42
memberabcdefgqwerty3-Jan-07 7:42 
GeneralRe: Nice Pin
Marc Clifton3-Jan-07 8:06
protectorMarc Clifton3-Jan-07 8:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    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 | Terms of Use | Mobile
Web02 | 2.8.160208.1 | Last Updated 20 Jan 2004
Article Copyright 2004 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid