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.
Tool | NSort Library |
Version covered | 1.0 |
Home page | |
Power Tools page | |
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 |
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.
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.
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.