Click here to Skip to main content
15,867,771 members
Articles / Programming Languages / C#

A QuickSort Algorithm With Customizable Swapping

Rate me:
Please Sign up or sign in to vote.
4.68/5 (30 votes)
19 Jan 20043 min read 139.6K   279   48   25
How to customize swapping function when sorting
If you ever need to customize the swapping function when sorting, then the class presented in this article will let 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 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:

C#
// 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:

C#
// 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:

C#
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:

C#
// 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:

C#
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:

C#
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

  • 20th 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.


Written By
Architect Interacx
United States United States
Blog: https://marcclifton.wordpress.com/
Home Page: http://www.marcclifton.com
Research: http://www.higherorderprogramming.com/
GitHub: https://github.com/cliftonm

All my life I have been passionate about architecture / software design, as this is the cornerstone to a maintainable and extensible application. As such, I have enjoyed exploring some crazy ideas and discovering that they are not so crazy after all. I also love writing about my ideas and seeing the community response. As a consultant, I've enjoyed working in a wide range of industries such as aerospace, boatyard management, remote sensing, emergency services / data management, and casino operations. I've done a variety of pro-bono work non-profit organizations related to nature conservancy, drug recovery and women's health.

Comments and Discussions

 
GeneralOther algorithm.... Pin
Super Lloyd2-May-07 20:22
Super Lloyd2-May-07 20:22 
GeneralGetting the Rank Pin
Michael Moreno23-Jan-06 23:07
Michael Moreno23-Jan-06 23:07 
GeneralComplexity Pin
Robert van Poelgeest24-Jan-04 7:03
Robert van Poelgeest24-Jan-04 7:03 
GeneralRe: Complexity Pin
Robert Rohde3-Feb-04 5:25
Robert Rohde3-Feb-04 5:25 
GeneralIList Pin
Jonathan de Halleux24-Jan-04 6:49
Jonathan de Halleux24-Jan-04 6:49 
GeneralRe: IList Pin
Marc Clifton24-Jan-04 6:55
mvaMarc Clifton24-Jan-04 6:55 
GeneralRe: IList Pin
Jonathan de Halleux24-Jan-04 9:48
Jonathan de Halleux24-Jan-04 9:48 
GeneralRe: IList Pin
Robert van Poelgeest26-Jan-04 3:05
Robert van Poelgeest26-Jan-04 3:05 
GeneralRe: IList Pin
Jonathan de Halleux26-Jan-04 6:27
Jonathan de Halleux26-Jan-04 6:27 
GeneralRe: IList Pin
Robert van Poelgeest27-Jan-04 0:04
Robert van Poelgeest27-Jan-04 0:04 
GeneralRe: IList Pin
Jonathan de Halleux25-Jan-04 7:25
Jonathan de Halleux25-Jan-04 7:25 
GeneralRe: IList Pin
Marc Clifton25-Jan-04 8:03
mvaMarc Clifton25-Jan-04 8:03 
GeneralRe: IList Pin
Jonathan de Halleux25-Jan-04 8:39
Jonathan de Halleux25-Jan-04 8:39 
GeneralQuisort -&gt; non static Pin
Jonathan de Halleux24-Jan-04 6:49
Jonathan de Halleux24-Jan-04 6:49 
GeneralDelegates Pin
Christopher Lord21-Jan-04 18:34
Christopher Lord21-Jan-04 18:34 
GeneralRe: Delegates Pin
Marc Clifton23-Jan-04 4:06
mvaMarc Clifton23-Jan-04 4:06 
GeneralNice Pin
Jonathan de Halleux20-Jan-04 9:02
Jonathan de Halleux20-Jan-04 9:02 
GeneralRe: Nice Pin
Marc Clifton20-Jan-04 10:50
mvaMarc Clifton20-Jan-04 10:50 
GeneralRe: Nice Pin
Jonathan de Halleux20-Jan-04 22:35
Jonathan de Halleux20-Jan-04 22:35 
GeneralRe: Nice Pin
Marc Clifton21-Jan-04 4:32
mvaMarc Clifton21-Jan-04 4:32 
GeneralRe: Nice Pin
Robert Rohde2-Feb-04 18:43
Robert Rohde2-Feb-04 18:43 
GeneralRe: Nice Pin
Marc Clifton3-Feb-04 1:29
mvaMarc Clifton3-Feb-04 1:29 
GeneralRe: Nice Pin
Marc Clifton3-Feb-04 1:43
mvaMarc Clifton3-Feb-04 1:43 
GeneralRe: Nice Pin
abcdefgqwerty3-Jan-07 6:42
abcdefgqwerty3-Jan-07 6:42 
GeneralRe: Nice Pin
Marc Clifton3-Jan-07 7:06
mvaMarc Clifton3-Jan-07 7: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.