4.8 Sorting Algorithms in C# with NSort

The NSort Library is a collection of sort methods utilizing customizable swap and compare methods. You can select an appropriate sort algorithm based on the data requirements, and, for complex data types, you can implement a custom comparer. You can also customize the swap method to accommodate any special requirements when swapping two data elements and easily exchange one sort algorithm for another using the ISort interface.

NSort Library at a Glance

Tool

NSort Library

Version covered

1.0

Home page

http://www.codeproject.com/csharp/cssorters.asp

Power Tools page

http://www.windevpowertools.com/tools/148

Summary

A collection of sorting algorithms in an extensible framework

License type

Unknown

Online resources

Code Project article at http://www.codeproject.com/csharp/cssorters.asp, forum

Supported Frameworks

.NET 1.1, 2.0

Getting Started

NSort’s sorting algorithms were written in C# with version 1.1 of the .NET Framework. They can also be used with C# 2.0 and version 2.0 of the .NET Framework, but generics are not supported. A separate version supporting generics is available from http://www.projectdistributor.net/Projects/Project.aspx?projectId=108.

To use the sorting algorithms, add a reference to the NSort assembly to your project’s assembly references. Alternatively, you can add the NSort.csproj file to your solution.

Using NSort

The NSort Library provides 15 different sort algorithms:

  • Bidirectional Bubble Sort

  • Bubble Sort

  • Combo Sort 11

  • Double Storage Merge Sort

  • Fast Quick Sorter

  • Heap Sort

  • In Place Merge Sort

  • Insertion Sort

  • Odd/Even Transport Sort

  • Quick Sort

  • Quick Sort with Bubble Sort

  • Selection Sort

  • Shaker Sort

  • Shear Sort

  • Shell Sort

These sorters vary in best- and worst-case sort times and in memory usage. Unfortunately, determining the optimal sorter isn’t always easy. It’s not just a matter of choosing one with the “best” worst-case sort time and the least amount of memory utilization. Performance depends on the size of your list and on how much of the data is already sorted. One sorter may perform very well under one set of conditions and poorly under a different set. For this reason, Quick Sort with Bubble Sort often makes a good default sorter. This sorter reverts to a Bubble Sort for small sets of data, which is more efficient than a Quick Sort. For large sets, it uses the Quick Sort algorithm first, then applies the Bubble Sort on the smaller fragments.

Using the sorters is straightforward. Decide which sorter you wish to use and instantiate it. Here’s an example that requests a Bubble Sort:

private ISorter sorter = new BubbleSorter( );

Next, create the list of items to be sorted. The Sort( ) method takes an IList representing an enumerable collection. For example, to sort a set of random numbers:

Random rnd = new Random( );
int[] list = new int[1000];

for(int i = 0;i<list.Length;++i)
{
  list[i] = rnd.Next( );
}

ArrayList mylist=new ArrayList(list);
sorter.Sort(mylist);

The default constructor for each of the sorters instantiates the ComparableComparer and DefaultSwap classes. These handle all value types and any class or struct implementing IComparable.

You can also customize the comparer and swapper by implementing IComparer and ISwap classes. All the sorters have an additional constructor:

public xxx(IComparer comparer, ISwap swapper)

This constructor can be used to specify your own compare and swap algorithms. This is a very useful feature of these classes, allowing you to sort not just value types, but also classes and structs that do not implement IComparable. Conversely, you can implement IComparable on your own classes to support custom comparisons.

Many of the sorters in NSort are ported from sorting demonstration code in Java, available at http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html.

For more information on sorting, refer to John Robbins’s MSDN article “Make Your Apps Fly with the New Enterprise Performance Tool,” available at http://msdn.microsoft.com/msdnmag/issues/04/12/EnterprisePerformance/default.aspx. You can also find an overview of sorting on Wikipedia at http://en.wikipedia.org/wiki/Sort_algorithms.

Getting Support

NSort is supported via the tool’s Code Project article at http://www.codeproject.com/csharp/cssorters.asp and at http://www.marcclifton.com.

Problems or questions can be posted in the comments section for the Code Project article or in the forum at Marc Clifton’s web site.

Get Windows Developer Power Tools now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.