Sorting is one of the fundamental operations in Computer Science. It not only shows up in CS 101, interviews but shows up very frequently in everyday computing. It also helps to build on top of – for starters, it is easier to search on sorted items.
Most sorting algorithms tend to perform some common operations in varying order. This post explores and provides implementations to them using C# 6.0.
Attribution
The first book on algorithms that I ever read and to this day, I re-read is Algorithms by Robert Sedgewick. Source codes below are direct implementation of his work.
Exchange Operation
As the name suggests, the operation exchanges two items. The implementation would also be very simple as following:
public void Exchange<T>(T item1, T item2)
{
T temp = item1;
item1 = item2;
item2 = temp;
}
The above code snippet makes the assumption that the generic type T is of reference type. However, since we are discussing the operation in the context of Sorting Algorithms, we would expect to be performing the operation on an array or a List.
Let’s re-write it to perform the exchange operation on an array of type T. For this, we will need to provide the indices that need to be exchanged. The code will look something like the following:
public void Exchange<T>(T[] items, int index1, int index2)
{
T temp = items[index1];
items[index1] = items[index2];
items[index2] = temp;
}
One obvious problem that we see here is that the code will fail if the caller provided indices that are out of bounds. It is debatable as to who should be performing bounds checking.
I am of the opinion that it does not matter, I would protect my code, not only by failing fast but also by providing tracing information so that it is easier to figure out where and what caused the failure. This is a good defensive programming practice.
Lets add the guard cases:
public void Exchange<T>(T[] items, int index1, int index2)
{
int arrayLength = items.Length;
// Guard cases
if (index1 < 0 || index1 >= arrayLength)
{
throw new IndexOutOfRangeException(
$"{nameof(index1)} (value: {index1}) is out of range " +
"for array {nameof(items)} (array length: {arrayLength}).");
}
if (index2 < 0 || index2 >= arrayLength)
{
throw new IndexOutOfRangeException(
$"{nameof(index2)} (value: {index2}) is out of range " +
"for array {nameof(items)} (array length: {arrayLength}).");
}
T temp = items[index1];
items[index1] = items[index2];
items[index2] = items[index1];
}
In their book, The Pragmatic Programmer: From Journeyman to Master, Hunt and Thomas introduced us to a principle called the DRY Principle – don’t repeat yourself. In that spirit, we should create a helper class that helps avoid bloating each method with redundant guard case checks. Marius Schulz has created a very elegant class (read about it here).
I have created a helper class of my own that provides some more functionality with tracing. Code for helper class is at the very end of this post.
Using my helper class, our method now looks like this:
public void Exchange<T>(T[] items, int index1, int index2)
{
// Guard cases
VerifyArgument.NotNull(items, nameof(items));
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1));
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2));
T temp = items[index1];
items[index1] = items[index2];
items[index2] = items[index1];
}
Similarly, we can create a method that handles enumerations that implement IList<T>:
public void Exchange<T>(IList<T> items, int index1, int index2)
{
// Guard cases
VerifyArgument.NotNull(items, nameof(items));
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1));
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2));
T temp = items[index1];
items[index1] = items[index2];
items[index2] = items[index1];
}
Compare Operation
The next operation that comes in handy is a way to compare two items. We need a way to tell our algorithms that given two items, which one is less-than, greater-than or in some cases equal to each other.
C# provides us two interfaces – the IEquatable and the IComparable interfaces. For our purposes, IComparable serves the purpose correctly. We can restrict our methods to only except a generic type if it implements IComparable interface and then utilize the IComparable<T>.CompareTo method.
To decide on what direction (sort order) we are sorting, we define an enumeration as following:
namespace Algorithms.Sorting
{
/// <summary>
/// Specifies the sort order.
/// </summary>
public enum SortOrder
{
Ascending,
Descending
}
}
Using the above enumeration and leveraging IComparable implementation, we can write a small helper method to encapsulate a Compare operation in a method that returns a boolean.
In case the sort order is defined SortOrder.Descending and the first argument is greater than the second argument, it returns true. For the case when sort order is defined as SortOrder.Ascending and the first argument is less than second argument, it returns true.
The method implementation looks like as following:
public bool Compare<T>(T itemCompareWith, T itemCompareTo, SortOrder sortOrder)
{
// Guard cases
VerifyArgument.NotNull(itemCompareWith, nameof(itemCompareWith), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(itemCompareTo, nameof(itemCompareTo), callerLineNumber, callerMemberName, callerFilePath);
if (sortOrder == SortOrder.Ascending)
{
return itemCompareTo.CompareTo(itemCompareWith) > 0;
}
return itemCompareTo.CompareTo(itemCompareWith) < 0;
}
We can also define another method that performs greater than or equal to (or less than or equal to) as follows:
public bool CompareOrEqual<T>(T itemCompareWith, T itemCompareTo, SortOrder sortOrder)
{
// Guard cases
VerifyArgument.NotNull(itemCompareWith, nameof(itemCompareWith), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(itemCompareTo, nameof(itemCompareTo), callerLineNumber, callerMemberName, callerFilePath);
if (sortOrder == SortOrder.Ascending)
{
return itemCompareTo.CompareTo(itemCompareWith) >= 0;
}
return itemCompareTo.CompareTo(itemCompareWith) <= 0;
}
Often times we need to perform a comparison operation and if that returns true, we need to perform an exchange as well. We can define another set of methods called CompareExchange.
Based on all the above operations, we can define a base class for Sorting Algorithms like following:
namespace Algorithms.Sorting
{
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using Algorithms.Common;
/// <summary>
/// The base class for sorting algorithms. Provides common functionality that is to be used to actual implementations.
/// </summary>
/// <typeparam name="T">The generic type T.</typeparam>
public abstract class SortBase<T> : ISortAlgorithm<T> where T : IComparable<T>
{
/// <summary>
/// Sorts a given array.
/// </summary>
/// <param name="items">The array of items to sort.</param>
public virtual void Sort(T[] items)
{
this.Sort(items, SortOrder.Ascending);
}
/// <summary>
/// Sorts a given array in the sort order specified.
/// </summary>
/// <param name="items">The array of items to sort.</param>
/// <param name="sortOrder">The sort order.</param>
public abstract void Sort(T[] items, SortOrder sortOrder);
/// <summary>
/// Sorts a given list.
/// </summary>
/// <param name="items">The list of items to sort.</param>
public virtual void Sort(IList<T> items)
{
this.Sort(items, SortOrder.Ascending);
}
/// <summary>
/// Sorts a given list in the sort order specified.
/// </summary>
/// <param name="items">The list of items to sort.</param>
/// <param name="sortOrder">The sort order.</param>
public abstract void Sort(IList<T> items, SortOrder sortOrder);
/// <summary>
/// Exchanges values between two indices of an array.
/// </summary>
/// <param name="items">The array to perform operation on.</param>
/// <param name="index1">The first index to exchange.</param>
/// <param name="index2">The second index to exchange.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
protected void Exchange(
T[] items,
int index1,
int index2,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard cases
VerifyArgument.NotNull(items, nameof(items), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
T temp = items[index1];
items[index1] = items[index2];
items[index2] = temp;
}
/// <summary>
/// Exchanges values between two indices of a list.
/// </summary>
/// <param name="items">The list to perform operation on.</param>
/// <param name="index1">The first index to exchange.</param>
/// <param name="index2">The second index to exchange.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
protected void Exchange(
IList<T> items,
int index1,
int index2,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard cases
VerifyArgument.NotNull(items, nameof(items), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
T temp = items[index1];
items[index1] = items[index2];
items[index2] = temp;
}
/// <summary>
/// Compares two items for greater than (in case sort order is ascending) or less than (in case sort order is descending).
/// </summary>
/// <param name="itemCompareWith">The item to compare with.</param>
/// <param name="itemCompareTo">The item whose CompareTo would be called.</param>
/// <param name="sortOrder">The sort order.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
/// <returns>Returns true if itemCompareWith is greater than itemCompareTo for SortOrder.Ascending.</returns>
protected bool Compare(
T itemCompareWith,
T itemCompareTo,
SortOrder sortOrder,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard cases
VerifyArgument.NotNull(itemCompareWith, nameof(itemCompareWith), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(itemCompareTo, nameof(itemCompareTo), callerLineNumber, callerMemberName, callerFilePath);
if (sortOrder == SortOrder.Ascending)
{
return itemCompareTo.CompareTo(itemCompareWith) > 0;
}
return itemCompareTo.CompareTo(itemCompareWith) < 0;
}
/// <summary>
/// Compares two items for greater than or equal to (in case sort order is ascending) or less than or equal to (in case sort order is descending).
/// </summary>
/// <param name="itemCompareWith">The item to compare with.</param>
/// <param name="itemCompareTo">The item whose CompareTo would be called.</param>
/// <param name="sortOrder">The sort order.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
/// <returns>Returns true if itemCompareWith is greater than itemCompareTo for SortOrder.Ascending.</returns>
protected bool CompareOrEqual(
T itemCompareWith,
T itemCompareTo,
SortOrder sortOrder,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard cases
VerifyArgument.NotNull(itemCompareWith, nameof(itemCompareWith), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(itemCompareTo, nameof(itemCompareTo), callerLineNumber, callerMemberName, callerFilePath);
if (sortOrder == SortOrder.Ascending)
{
return itemCompareTo.CompareTo(itemCompareWith) >= 0;
}
return itemCompareTo.CompareTo(itemCompareWith) <= 0;
}
/// <summary>
/// Compares and exchanges two items in an array.
/// </summary>
/// <param name="items">The array of items.</param>
/// <param name="index1">The index of first item to compare.</param>
/// <param name="index2">The index of second item to compare.</param>
/// <param name="sortOrder">The sort order.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
protected void CompareExchange(
T[] items,
int index1,
int index2,
SortOrder sortOrder,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard case
VerifyArgument.NotNull(items, nameof(items), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(items[index1], $"{nameof(items)}[{index1}]", callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(items[index2], $"{nameof(items)}[{index2}]", callerLineNumber, callerMemberName, callerFilePath);
if (!this.Compare(items[index2], items[index1], sortOrder, callerLineNumber, callerMemberName, callerFilePath))
{
this.Exchange(items, index1, index2, callerLineNumber, callerMemberName, callerFilePath);
}
}
/// <summary>
/// Compares and exchanges two items in an array.
/// </summary>
/// <param name="items">The array of items.</param>
/// <param name="index1">The index of first item to compare.</param>
/// <param name="index2">The index of second item to compare.</param>
/// <param name="sortOrder">The sort order.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
protected void CompareExchange(
IList<T> items,
int index1,
int index2,
SortOrder sortOrder,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
// Guard case
VerifyArgument.NotNull(items, nameof(items), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNegative(index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index1, nameof(index1), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.IndexNotOutOfRange(items, nameof(items), index2, nameof(index2), callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(items[index1], $"{nameof(items)}[{index1}]", callerLineNumber, callerMemberName, callerFilePath);
VerifyArgument.NotNull(items[index2], $"{nameof(items)}[{index2}]", callerLineNumber, callerMemberName, callerFilePath);
if (!this.Compare(items[index2], items[index1], sortOrder, callerLineNumber, callerMemberName, callerFilePath))
{
this.Exchange(items, index1, index2, callerLineNumber, callerMemberName, callerFilePath);
}
}
}
}
Notice that the class above is abstract and implements an interface called ISortAlgorithm. The interface comes in handy by letting the caller choose a particular sort algorithm implementation to use. It’s definition looks like:
namespace Algorithms.Sorting
{
using System.Collections.Generic;
/// <summary>
/// The sorting algorithm contract.
/// </summary>
/// <typeparam name="T">A generic type T.</typeparam>
public interface ISortAlgorithm<T>
{
/// <summary>
/// Sorts a given array in ascending order.
/// </summary>
/// <param name="items">The array of items to sort.</param>
void Sort(T[] items);
/// <summary>
/// Sorts a given array in the sort order specified.
/// </summary>
/// <param name="items">The array of items to sort.</param>
/// <param name="sortOrder">The sort order.</param>
void Sort(T[] items, SortOrder sortOrder);
/// <summary>
/// Sorts a given list in ascending order.
/// </summary>
/// <param name="items">The list of items to sort.</param>
void Sort(IList<T> items);
/// <summary>
/// Sorts a given list in the sort order specified.
/// </summary>
/// <param name="items">The list of items to sort.</param>
/// <param name="sortOrder">The sort order.</param>
void Sort(IList<T> items, SortOrder sortOrder);
}
}
The interface helps us expose a contract for consumers to know what the method calls are while the base class provides implementation of helper methods that we discussed above. This is a design choice that helps us have common functionality in one place (to stay true to the DRY principle) yet keep the contract light-weight.
This sets up a good foundation to start implementing actual sorting algorithms.
The VerifyArgument Class
namespace Algorithms.Common
{
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
/// <summary>
/// The <cref="VerifyArgument"/> class. Defines helper methods to verify and validate arguments.
/// </summary>
public static class VerifyArgument
{
/// <summary>
/// Verifies whether a given argument was null. Throws <cref="ArgumentNullException"/> if argument was null.
/// </summary>
/// <param name="argumentValue">The value of the argument.</param>
/// <param name="argumentName">The name of the argument.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
public static void NotNull<T>(
T argumentValue,
string argumentName,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
if (typeof(T).IsValueType)
{
// Shorthand value types.
return;
}
if (argumentValue == null)
{
throw new ArgumentNullException(
argumentName,
$"Argument {argumentName} was expected to be not null. At {callerMemberName} " +
$"in file {callerFilePath} at line {callerLineNumber}");
}
}
/// <summary>
/// Verifyes whether a given string was null or empty. Throws <cref="ArgumentNullException"/> if argument was null or empty.
/// </summary>
/// <param name="argumentValue">The value of the argument.</param>
/// <param name="argumentName">The name of the argument.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
public static void NotNullOrEmpty(
string argumentValue,
string argumentName,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
if (string.IsNullOrEmpty(argumentValue))
{
throw new ArgumentNullException(
argumentName,
$"Argument {argumentName} was expected to be not null and not empty. At {callerMemberName} " +
$"in file {callerFilePath} at line {callerLineNumber}");
}
}
/// <summary>
/// Verifies whether a given integer was non-negative. Throws <cref="ArgumentException"/> if argument was negative.
/// </summary>
/// <param name="argumentValue">The value of the argument.</param>
/// <param name="argumentName">The name of the argument.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
public static void NotNegative(
int argumentValue,
string argumentName,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
if (argumentValue < 0)
{
throw new ArgumentException(
$"Argument {argumentName} was expected to be non-negative. At {callerMemberName} " +
$"in file {callerFilePath} at line {callerLineNumber}",
argumentName);
}
}
/// <summary>
/// Verifies whether a given index was out of range. Throws <cref="IndexOutOfRangeException /> if index was out of range.
/// </summary>
/// <typeparam name="T">The generic type T.</typeparam>
/// <param name="array">The list to check for range.</param>
/// <param name="arrayName">The name of the list.</param>
/// <param name="index">The index value to check.</param>
/// <param name="indexName">The name of the index.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
public static void IndexNotOutOfRange<T>(
T[] array,
string arrayName,
int index,
string indexName,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
int length = array.Length;
if (index >= length || index < 0)
{
throw new IndexOutOfRangeException($"{indexName} (value: {index}) is out of range for array {arrayName} (array length: {length}). At {callerMemberName} " +
$"in file {callerFilePath} at line {callerLineNumber}");
}
}
/// <summary>
/// Verifies whether a given index was out of range. Throws <cref="IndexOutOfRangeException /> if index was out of range.
/// </summary>
/// <typeparam name="T">The generic type T.</typeparam>
/// <param name="array">The list to check for range.</param>
/// <param name="listName">The name of the list.</param>
/// <param name="index">The index value to check.</param>
/// <param name="indexName">The name of the index.</param>
/// <param name="callerLineNumber">The caller line number.</param>
/// <param name="callerMemberName">The caller member name.</param>
/// <param name="callerFilePath">The caller file path.</param>
public static void IndexNotOutOfRange<T>(
IList<T> list,
string listName,
int index,
string indexName,
[CallerLineNumber] int callerLineNumber = 0,
[CallerMemberName] string callerMemberName = "",
[CallerFilePath] string callerFilePath = "")
{
int count = list.Count;
if (index >= count || index < 0)
{
throw new IndexOutOfRangeException($"{indexName} (value: {index}) is out of range for array {listName} (array length: {count}). At {callerMemberName} " +
$"in file {callerFilePath} at line {callerLineNumber}");
}
}
}
}
Usman Sharif 
1 Comment