Sorting is an issue that traces way back to the beginning of programming. All programming languages provide different ways to sort different items. Many even allow you to implement your own comparison function so you can sort a list of items in any way you want; by length or string, in reverse order, string with the most spaces, etc. But, I ran into a sorting problem that couldn’t easily be solved by any built in functions. My problem is as follows: the application I’m writing allows the user to post transactions to a resident in an apartment and each transaction is associated with a category. Categories include Rent, Pet Fees, Late Fees, Storage Unit Charge, Garage Charge, Carport Charge, etc. When the user posts a payment, the payment needs to be applied to the various oustanding charges for the resident in an order that can be arbitrarily set by an administrator. For instance, if a user has an outstanding rent charge, late fee charge, and garage charge, an administrator could setup the application so that the payment would first be applied to the late fee, then the garage charge, and lastly the rent charge. So, when a payment is made, the outstanding charges need to be retrieved, and then ordered according to what the user has defined. There in lies the problem. I wasn’t trying to sort a list by length, alphabetically, or something simple like that, I needed to sort the list by the ordering in another list defined by the user.
To solve my problem, I built an anonymous typed class called ArbitrarySort that implements the IComparer interface. The constructor takes a List of objects of type T which defines the desired sort order. From the passed in List, a Dictionary with key of type T and value of type int is created. Each item in the List is added in order into the Dictionary with an associated value that is incremented by one after each addition. Thus, if you passed in the List
Dog
Cat
Mouse
Hampster
the corresponding Dictionary in (Key, Value) form would be:
(Dog, 1)
(Cat, 2)
(Mouse, 3)
(Hampster, 4)
The Compare method takes two arguments of type T and looks up the value associated with each item in the Dictionary and compares them. Thus, if the Compare method was called on “Hampster” and “Cat”, the method would compare the values 4 and 2 and 1 would be returned as “Hampster” is considered to be greater than “Cat” and comes later in the list.
With this class, I can pass in a list of all transaction categories ordered according to which category a payment should be applied first and then when a payment is received, a list of outstanding charges is sorted according to the predefined order in the ArbitrarySort class.
/// <summary>
/// Creates a sorting class that lets you sort a list of items in an arbitrary order.
/// </summary>
/// <typeparam name="T"></typeparam>
public class ArbitrarySort<T> : IComparer<T>
{
/// <summary>
/// Dictionary that stores the objects used for ordering. The key represents the
/// object that is to be stored and the value is the index in the list. Retrieving
/// the value of an object will give the index it appears in the list.
/// </summary>
Dictionary<T, int> _sortOrder;
/// <summary>
/// Constructs a new ArbitrarySort class to sort a list in an abritrary order.
/// </summary>
/// <param name="sortOrder">Specifies the order in which items should be ordered.
/// Example: To sort a list of single digit integers first by even numbers and then odd numbers, pass in { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 }.</param>
public ArbitrarySort(List<T> sortOrder)
{
// Create the dictionary
_sortOrder = new Dictionary<T, int>();
for (int i = 0; i < sortOrder.Count(); i++)
_sortOrder.Add(sortOrder[i], i);
}
/// <summary>
/// Compares two objects and returns a value indicating whether one is less than, equal to or greater than the other.
/// </summary>
/// <param name="x">First object of type T to compare.</param>
/// <param name="y">Second object of type T to compare</param>
/// <returns>If x is less than y then -1. If x is equal to y then 0. If x is greater than y then 1</returns>
public int Compare(T x, T y)
{
// Perform null testing. A null reference is considered to be less
// than the other object
if (x == null && y == null)
return 0;
else if (x == null)
return -1;
else if (y == null)
return 1;
else
{
// Variables to store the indicies in the original sort order of each of the objects
int xIndex = 0;
int yIndex = 0;
// Try and get both objects from the _sortOrder collection
bool xExists = _sortOrder.TryGetValue(x, out xIndex);
bool yExists = _sortOrder.TryGetValue(y, out yIndex);
// If one object is not in the list it is considered to be
// greater than the other object. Otherwise, compare the two
// indicies, if the index for object x is less than object y,
// then x is smaller than y and visa versa.
if (!xExists && !yExists)
return 0;
else if (!xExists)
return 1;
else if (!yExists)
return -1;
else
return xIndex.CompareTo(yIndex);
}
}
}
Since the AribitrarySort class is implemented using a Dictionary, which provides O(1) lookup time, the sorting of lists is extremely quick. For example, sorting a list of one million elements only took 2.6 seconds. For reference, sorting the same list alphabetically using the generic quick sort implemented in the .Net Framework took 1.9 seconds.
Random random = new Random(DateTime.Now.Millisecond);
List<string> sortOrder = new List<string>() { "Dog", "Cat", "Fish", "Bird", "Rat", "Monkey", "Frog", "Snake", "Spider", "Lizard", "Rabbit" };
List<string> arbitrarySortList = new List<string>();
List<string> quickSortList = new List<string>();
for (int i = 0; i < 1000000; i++)
{
string item = sortOrder[random.Next(0, 9)];
arbitrarySortList.Add(item);
quickSortList.Add(item);
}
Stopwatch sw = Stopwatch.StartNew();
arbitrarySortList.Sort(new ArbitrarySort<string>(sortOrder));
sw.Stop();
Console.WriteLine("Arbitrary Sort Time: " + sw.ElapsedMilliseconds + " ms");
sw.Reset();
sw.Start();
quickSortList.Sort();
sw.Stop();
Console.WriteLine("Quick Sort Time: " + sw.ElapsedMilliseconds + " ms");
// Output
// ------
// Arbitrary Sort Time: 2628 ms
// Quick Sort Time: 1938 ms
Nick Olsen's Programming Tips 