A QuickSort Algorithm With Customizable Swapping






4.68/5 (27 votes)
Jan 20, 2004
3 min read

141674

279
How to customize swapping function when sorting
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 string
s, 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 string
s. 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.