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

Sorting Algorithms In C#

, ,
Rate me:
Please Sign up or sign in to vote.
4.77/5 (47 votes)
4 Feb 20044 min read 345K   2.6K   193   34
A collection of sorting algorithms implementing customizable comparitor and swapper functions
This library provides a very nice and flexible package of sorting algorithms from which the developer can choose.

Preface

By Marc Clifton

After my last article on a QuickSort algorithm with customizable swapping, Jonathan de Halleux made some improvements to my original design and added some sorting algorithms. As I was writing this article and waiting for Jonathan's blessing, Robert Rohde provided some additional sorting algorithms which I have included here as well. Rather than updating the original article, I felt it would be better to represent Jonathan's and Robert's work separately from my original article, as they have contributed so much that it is quite a different beast. My contribution at this point is the article itself, some additions to the ISwap interface, and integrating both Jonathan's and Robert's work into a unified namespace. All kudos should go to Jonathan's and Robert's excellent work--I learned a few things writing this article!

Introduction

This library provides a very nice and flexible package of sorting algorithms from which the developer can choose. The algorithms presented here have been ported to C# and are based on selected algorithms in Java found here. Click on the pictures to run an applet that shows the algorithm running!

The sorting algorithms are:

  • Bidirectional Bubble Sort
  • Bubble Sort
  • ComboSort11
  • Double Storage Merge Sort (utilizes setter)
  • Fast Quick Sort (utilizes setter)
  • Heap Sort
  • In Place Merge Sort (utilizes setter)
  • Insertion Sort (utilizes setter)
  • Odd-Even Transport Sort
  • Quick Sort
  • Quick Sort With Bubble Sort (utilizes setter)
  • Selection Sort
  • Shaker Sort
  • Shear Sort
  • Shell Sort

Sorting algorithms such as InPlaceMergeSort, InsertionSort, and ShellSort perform set operations rather than swap operations. For this reason, the ISwap interface includes two "Set" methods. If you aren't using one of the algorithms that uses a setter, then you can ignore them.

All of these sort algorithms are thread safe.

The Object Model

The object model easily allows for additional sorting algorithms to be added. The following UML diagram illustrates this with the FastQuickSorter implementation:

Image 1

Additional sorters are derived from SwapSorter.

Implementation

The following illustrates some of the key implementation features of the NSort library.

Interfaces

Two interfaces provide the necessary abstraction of concrete instances.

ISorter

C#
using System;
using System.Collections;

namespace NSort
{
    /// <SUMMARY>
    /// Summary description for ISorter.
    /// </SUMMARY>
    public interface ISorter
    {
        void Sort(IList list);
    }
}

This interface abstracts the concrete sorting algorithms.

ISwap

C#
using System;
using System.Collections;

namespace NSort
{
    /// <SUMMARY>
    /// Object swapper interface
    /// </SUMMARY>
    public interface ISwap
    {
        void Swap(IList array, int left, int right);
        void Set(IList array, int left, int right);
        void Set(IList array, int left, object obj);
    }
}

This interface abstracts the concrete swapper. In some cases, additional work needs to be done when swapping elements of the array. Defining your own swapping algorithm derived from the ISwap interface allows you to accomplish this work.

SwapSorter

This is the abstract base class for all the sorting algorithms. It implements the management of the concrete ISwap and ISorter instances. Each concrete sorting algorithm implements two constructors--a default constructor and a constructor in which you can specify your own comparer and swapper functions. In the SwapSorter class, these are implemented as follows:

C#
public SwapSorter()
{
    this.comparer = new ComparableComparer();
    this.swapper = new DefaultSwap();
}

As you can see from the default constructor above, the default comparer and swapper are implemented.

C#
public SwapSorter(IComparer comparer, ISwap swapper)
{
    if (comparer == null)
        throw new ArgumentNullException("comparer");
    if (swapper==null)
        throw new ArgumentNullException("swapper");

    this.comparer = comparer;
    this.swapper = swapper;
}

The above code illustrates specifying your own comparer and swapper.

An instance of the default comparer or swapper can also be passed in, should you only need to specify your own instance of one or the other, but not both.

DefaultSwap

The default swapper implementation is straight-forward:

C#
using System;
using System.Collections;

namespace NSort
{
    /// <SUMMARY>
    /// Default swap class
    /// </SUMMARY>
    public class DefaultSwap : ISwap
    {
        public void Swap(IList array, int left, int right)
        {
            object swap=array[left];
            array[left]=array[right];
            array[right]=swap;
        }

        public void Set(IList array, int left, int right)
        {
            array[left]=array[right];
        }

        public void Set(IList array, int left, object obj)
        {
            array[left]=obj;
        }
    }
}

ComparableComparer

The default comparer is very powerful: 

C#
using System;
using System.Collections;

namespace NSort
{
    /// <SUMMARY>
    /// Default <SEE cref="IComparable" /> object comparer.
    /// </SUMMARY>
    public class ComparableComparer : IComparer
    {
        public int Compare(IComparable x, Object y)
        {
            return x.CompareTo(y);
        }

        #region IComparer Members
        int IComparer.Compare(Object x, Object y)
        {
            return this.Compare((IComparable)x,y);
        }

        #endregion
    }
}

Notice in this implementation, the IComparer.Compare method invokes the object's ICompareTo function. This has the advantage of putting the comparison "smarts" into the object being compared against. There are several advantages to this. If the object is a class, only certain fields in the class might be involved in the comparison. Also, the object itself can determine what other types of objects it can be compared with and provide necessary translation/conversion services. Given this flexibility, overriding the comparer is probably only necessary when comparing third party objects that do not implement CompareTo or in cases where you wish to extend the native CompareTo capability.

Usage

The usage is best illustrated by looking at the NUnit-compatible unit tests that are provided with the download.

Instantiating the Sorter

Each sorting algorithm has its own test fixture:

C#
[TestFixture]
public class QuickSorterTest : SorterTest
{
    [SetUp]
    public void SetUp()
    {
        this.Sorter = new QuickSorter();
    }
}

Creating, Sorting, And Verifying Some Sample Data

The test, verifying that the sorter is behaving correctly:

C#
[Test]
public void SortInt()
{
    Random rnd = new Random();
    int[] list = new int[1000];
    int i;
    for(i = 0; i<list.Length; ++i)
        list[i] = rnd.Next();

    // create sorted list
    SortedList sl = new SortedList();
    foreach(int key in list)
        sl.Add(key,null);

    // sort table
    Sorter.Sort(list);

    i = 0;
    foreach(int val in sl.Keys)
    {
        Assert.AreEqual(val,list[i]);
        ++i;
    }
}

Unit Testing

Image 2

The code includes unit tests written for Marc's unit test framework. In the code included in this article, the unit tests are part of the NSort assembly.

Speaking of which, beware of the fast quicksort algorithm--the unit test fail on this once, but since the test data is randomly generated, it hasn't been reproduced!

What's Next

Jonathan has written an excellent performance benchmark framework that will readily integrate into Marc's unit test framework. The next step is to do so, and illustrate that effort by benchmarking the various sorting algorithms.

History

  • 5th February, 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.

Written By
Engineer
United States United States
Jonathan de Halleux is Civil Engineer in Applied Mathematics. He finished his PhD in 2004 in the rainy country of Belgium. After 2 years in the Common Language Runtime (i.e. .net), he is now working at Microsoft Research on Pex (http://research.microsoft.com/pex).

Written By
Web Developer
Germany Germany
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionFYI: How to Use With PowerShell V3 under Win7 Pin
chuckmoore5520-Dec-12 12:01
chuckmoore5520-Dec-12 12:01 
GeneralMy vote of 5 Pin
csharpbd22-Nov-12 1:10
professionalcsharpbd22-Nov-12 1:10 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey28-Mar-12 0:13
professionalManoj Kumar Choubey28-Mar-12 0:13 
QuestionA Really fast implementation Pin
Mehdi Gholam4-Jan-12 3:08
Mehdi Gholam4-Jan-12 3:08 
GeneralMy vote of 5 Pin
ayslix8-Jan-11 3:51
ayslix8-Jan-11 3:51 
i liek 'em gifs
GeneralUpdated generic version Pin
Kriszta8314-Mar-10 4:44
Kriszta8314-Mar-10 4:44 
GeneralGreat Job Pin
Kanou9217-Sep-09 23:38
Kanou9217-Sep-09 23:38 
GeneralGreat job! Pin
crmckenzie13-Oct-05 7:49
crmckenzie13-Oct-05 7:49 
Generalfast quicksort Pin
IdUnknown12-Jul-05 18:57
IdUnknown12-Jul-05 18:57 
GeneralUnique Sort Pin
Brad_Jones19-May-05 8:41
Brad_Jones19-May-05 8:41 
GeneralUpdated version on ProjectDistributor. Pin
Jonathan de Halleux10-May-05 5:01
Jonathan de Halleux10-May-05 5:01 
GeneralYou code does not work. Pin
Code Deamon7-Mar-05 7:19
Code Deamon7-Mar-05 7:19 
GeneralRe: You code does not work. Pin
Dr Reedo15-Sep-05 5:50
Dr Reedo15-Sep-05 5:50 
GeneralRe: You code does not work. Pin
Geomancy19-Jul-06 5:18
Geomancy19-Jul-06 5:18 
GeneralRe: You code does not work. Pin
Tariq H19-Dec-06 12:18
Tariq H19-Dec-06 12:18 
GeneralCopyright notices Pin
Mathew Hall18-Feb-05 15:50
Mathew Hall18-Feb-05 15:50 
GeneralRe: Copyright notices Pin
Marc Clifton19-Feb-05 6:16
mvaMarc Clifton19-Feb-05 6:16 
GeneralRe: Copyright notices Pin
Mathew Hall19-Feb-05 14:54
Mathew Hall19-Feb-05 14:54 
GeneralMSDN Mention Pin
Paul Watson22-Nov-04 23:31
sitebuilderPaul Watson22-Nov-04 23:31 
GeneralThis merge sort implementation not stable Pin
Jeffrey Nichols17-Nov-04 8:56
Jeffrey Nichols17-Nov-04 8:56 
GeneralMerging Sorting algorithms in NCollection Pin
Jonathan de Halleux30-Mar-04 8:09
Jonathan de Halleux30-Mar-04 8:09 
GeneralDetect Devices Connected On USB Pin
Faheem Farooqui30-Mar-04 4:27
sussFaheem Farooqui30-Mar-04 4:27 
GeneralRe: Detect Devices Connected On USB Pin
sheniss23-May-06 23:50
sheniss23-May-06 23:50 
Questioncopy right ? Pin
T Manjaly22-Mar-04 11:28
T Manjaly22-Mar-04 11:28 
AnswerRe: copy right ? Pin
Marc Clifton22-Mar-04 12:55
mvaMarc Clifton22-Mar-04 12:55 

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.