Submitted by BillB on no date available

(If you have a minute, please add a comment when you're done so I know if I'm presenting this well enough.)

Sorting a List of Custom Objects in C#

Contents

• Sorting is about Comparing
• System.Int32.CompareTo()
• Sorting A List Of Integers
• Sorting A List Of Custom Objects
• Generic vs. Non-Generic Versions
• Sort() - IComparable.CompareTo
• Sort(IComparer<T>) - IComparer.Compare
• Sort(Comparison<T> comparison)
• Recap
• Wacky Sorts
• Lessons Learned
• Play Time

This article is about IComparable and IComparer and how they're used to sort a collection in place, meaning it actually changes the order of the items in the collection. Alternatively, you could leave the collection in it's original order and receive objects in sorted order by using LINQ to Objects, a set of C# 3.0 extension methods in the System.Linq.Enumerable<T> class. I have another article on LINQ to Objects if you're interested. When you're done here, I hope you'll feel confident using Sort for any crazy sorting requirements your business throws at you.

I start very basic, sorting a list of ints, to make sure you understand the basics of sorting in .Net. Then I move on to sorting a list of custom objects using the various Sort overrides. At the end I show how flexible sorting can be so you get a feel for dealing with unusual sorting requirements.

Sorting is about Comparing 

To sort a list of objects, you need to compare the items in the list to one another somehow. But the Sort algorithm doesn't do the comparison; it can't know how you want to compare two custom objects to one another. Or say you want to customize the sort of a list of .Net objects, like ints; maybe you want them in reverse order or you want evens then odds descending: 10-8-6-4-2-9-7-5-3-1. (Hmm, how would you code that?) So, it makes sense that the comparison is implemented in code that resides in the application that calls Sort, most likely in the class that describes the objects being sorted but maybe in a class built just to support sorting.

There is a category of sort algorithms called comparison sorts which includes what's called quicksort, the algorithm behind List<T>.Sort. The sorting algorithm itself is located in the .Net framework but it calls back to code located in the calling application; like I said, probably in the class of the object it's sorting but it could be anywhere. The type being sorted can be a .Net type, like Int32, or a custom type. Only the type knows how to decide relative values between objects; does object x come before or after object y. So, in .Net, to customize a sort you customize the comparison done in the type being sorted.

For the .Net beginner, a discussion of sorting is a good place to emphasize the concept of a framework, (or software library), calling back to the application that called the framework in the first place. A framework can't do everything; it needs help from the application calling on it; there's always something that the framework can't know how to do for all of it's clients. The clients of the framework provide those pieces. In this case, the piece is how to compare two objects. I have another article on C# Callbacks, which shows how callbacks are done with an interface and with a delegate.

System.Int32.CompareTo() 

Before getting into sorting a list of custom obejcts, let's begin with the basics by sorting a list of ints. And as I just mentioned, to sort we have to understand how to compare. All the .Net data types, like Decimal, Int32 and String implement the IComparable interface and so, implement a method named CompareTo, which will compare the instance value with another value of the same type and "return an indication of their relative values" - MSDN.

Here's the System.Int32 Struct definition:

Here's the CompareTo() method for System.Int32 and how it's called :

That indication that CompareTo returns is an int and will have a value of:

• 0 if the ints are equal (myInt == yourInt)
• 1 if the instance int is greater than the parameter int (myInt > yourInt)
• -1 if the instance is less than the parameter int (myInt < yourInt)

Sorting A List Of Integers (List<int>.Sort) 

As I mentioned in the introduction, the Sort method doesn't know how to compare two objects of a particular type. The type itself will have to provide that service to the Sort method. As the sort algorithm runs, it will call back to the type whenever it needs to do another compare operation. We just saw how Int32 implements a CompareTo method and that's the method that List<int>.Sort will call when it's sorting a List of integers. Read my article on callbacks if you're unfamiliar with the callback concept or how C# interfaces provide a contract between a software library or framework and an application that uses it.

So, let's say you're sorting a List<int>, called myInts. myInts.Sort() will call the IComparable.CompareTo method implemented in the System.Int32 struct to find out how to decide if one int comes before or after another.

Sorting A List Of Custom Objects (List<T>.Sort) 

Just like System.Int32, your custom class can implement IComparable.CompareTo where you'll write code to compare two objects of your type and return a -1, 0 or 1 indicating the sort order between the two. Before we do that, I'll mention that there are other options that are revealed by the other overrides available on List<T>.Sort :

• List<T>.Sort() - The type you're sorting must implement IComparable.CompareTo.
• List<T>.Sort(IComparer<T>) - Your comparing logic is passed as a reference to an object that implements IComparer.Compare.
• List<T>.Sort(int index, int count, IComparer<T>) - Same as the previous one but limits sorting to a range of elements in the list.
• List<T>.Sort(Comparison<T>) - Your comparing logic is passed as a delegate object.

We'll see it all but for now we'll stick to the simple situation of sorting a list of custom objects on a single property of a .Net data type, like a String or an Int32. But first I promised to talk about the generic vs. the noon-generic version of the IComparable interface.

Generic vs. Non-Generic Versions 

I'm going to ignore the non-generic versions of IComparable and IComparer in this article because I wouldn't use them; at least I don't know when I would use them. I suppose if I wanted to have a list of objects where each item could be of a different type; an int, then, say, a Car object then a string and so on. Not sure why I'd do this, but I'm sure there's a reason out there. If you use the non-generic versions, you have to cast an object to the type you're sorting:

If you implement the generic version, no casting required:

Then there's the performance benefit of avoiding boxing and unboxing of value types; another topic for another day.

Sort() - IComparable.CompareTo 

Finally, on to sorting custom objects. We'll begin with creating a default sort for a list of custom objects, in this case Car objects. By default sort I mean the sort that is done when List<Car>.Sort() is called with no arguments. We now know that to do that we need to implement IComparable.CompareTo in our Car class. Lets say we want the default sort to be on the Price property of a Car object. To do that we'll implement IComparable.CompareTo in our Car class and write code that indicates sort order based on car prices.

Decimal.CompareTo returns an int and the int is always either -1, 0 or 1. In our car price sort, it's -1 if the price of the car object instance that's calling CompareTo is less than the price of the car object that's passed in. 0 if they're the same and +1 if the instance object's price is greater. (This is what the commented out code does. I put it there to emphasize the fact that CompareTo returns a -1, o or 1.) Here's what MSDN says about Decimal.CompareTo. The code that's actually calling your Car.CompareTo method is in the framework, somewhere inside the List.Sort method and it's using the int return value to accomplish it's sort.

And to do the sort:

Sort(IComparer<T>) - IComparer.Compare 

Usually you'll want the flexibility to sort a list of custom objects on any property, not just one. You wouldn't use IComparable.CompareTo on your Car class because it doesn't make sense to put information that indicates how to sort a List of Cars in a Car class that describes a single Car object. (You could though, by adding a state to your type that would indicate how to sort and logic in CompareTo that would do different compares based on the state.) It's makes more sense to put all the information that describes various ways to sort a list of a custom objects into it's own class, one that implements IComparer.Compare.

CompareTo is called on an instance of an object being compared, passing in an object to compare itself to. IComparer.Compare takes both objects being compared as arguments.

IComparer.Compare() enables you to specify a property to sort on when calling the Sort in the form of an argument to the IComparer class constructor. So you can call Sort like:

It's common to use an enum for the various sort criteria, as I've done here.

A quick revist to the topic of interfaces. I mentioned that before an interface provides a contract between the Sort method and your code. Interface polymorphism refers to the fact that an instance of any object that implements an interface can be referred to using the name of that interface. So, the same code in List<T>.Sort(IComparer<T>) method can be called with your IComparer class name, myList(MyComparer), and also myList(YourComparer) it will call back to the appropriate IComparer class.

To illustrate, I'm borrowing from this well written blog, http://devcenter.auburnrandall.com/Default.aspx?type=post&id=86, where I got my first sorting lesson. I'll be fleshing that example out as we go along here. I particularly liked the way the auburnrandall blog broke up the coding into 5 different steps. This is a very common pattern and no wonder; it's very clean and clear in purpose. I'm starting to get into some more unusual sorting criteria in this example, with the a sort by Make in reverse and a sort by Price that first doubles the price of Fords.

So, you write an IComparer class with all the different ways to compare two objects. You instantiate the IComparer class and tell it which comparison to use in a constructor call. Finally, you call Sort, passing it the reference to your IComparer object. When you want to sort on different criteria, you create a new IComparer class and call Sort again. Note that you can always have a default sort by implementing IComparable in your custom class AND create an IComparer class as well.

Sort(Comparison<T> comparison) 

On to the third Sort override. In some circumstances a delegate in the form of an anonymous method could be used as a Sort() parameter, enabling you to forgo implementing the IComparable interface by your custom class. Usually you want to keep anonymous methods short, so you'd use this override if all you're doing in your CompareTo method is calling the default CompareTo for the type you're sorting, like I did when sorting by Car.Price. You'd also consider this override if you don't care about code reuse, like you'd get with an IComparer class. Delegates are great for low overhead, (no extra classes or named methods to code), solutions that are expressive, (the sort criteria is sitting right in front of you when you read the call to Sort). Lambda syntax can increase the expressiveness.

Here's the signature from MSDN:

OK, so let's look up what a Comparison<T> is; it's a delegate type provided by .Net:

Don't freak out. Just replace any T with your type.

This is why we can pass a delegate to the Sort method. Our delegate is a Comparison object; a delegate that returns an int and takes two arguments of the same type; Cars, in this example.

So, using a delegate, you can eliminate IComparable.CompareTo() and IComparer.Compare(). Here we'll sort a list of Car objects based on the Car.Make property, a string:

If you want some more info on delegates and lambda syntax, I've got another article that explains a bit about Delegates, Anonymous methods and Lambdas.

Recap 

• Sorting in general
• .Net data types support sorting with a method that tells how to compare two objects of the type
• Three overloads of List<T>.Sort
• IComparable
• IComparer - A common .Net pattern
• Comparison

Wacky Sorts 

What if your sorting needs are more unique, requiring more than compares of simple data types. Let's say your requirement is to sort on some criteria that has nothing to do with whether 1 comes before 2 or "Apple" comes before "Watermelon". Maybe you need to sort on say, population / square miles * average number of goats per household. Who knows what's valuable to the business. That kind of thing isn't built into the framework; there's no CompareTo for that.

What if we wanted to sort by Car.Model but always wanted Fords to appear at the top of the sort. Here's a CompareTo method to do that:

So you see, you don't need to "nest" calls to CompareTo, like when you're just comparing simple data types straight across; an int compared to an int, for example. You can return 1,0 or -1 based on any old logic. BTW, if this sort was in an IComparer class, you could make it more flexible, by adding a constructor to the IComparer class to take a param that says which Car make to always keep on top.

Lessons Learned 

• A separate IComparer class is commonly used for sorting lists of custom objects by various object properties.
• CompareTo and Compare always return either a 1, 0 or -1 and are called by a sorting algorithm inside .Net to accomplish it's sort.
• If your collection is a List<T>, you can use a Comparison delegate for quick and simple sorts and reduce code size.
• You can do whatever you want in CompareTo and Compare to manipulate a sort, as long as you return -1, 0 or 1.

Play Time 

As you can see in the example app below, I've written a couple of sorts that are a little more custom; a reverse sort and a sort that doubles the price of a Ford. The reverse sort is still just one line of code, (the objects are just switched), but the FordDoublePrice requires more code. There's also a sort by Car.Make that always keeps Ford at the top of the list. You can imagine that in the real world these types of custom sorts come up all the time and can require lots of code. If you need lots of code to accomplish a sort, then a whole IComparer class makes sense. But if your specifications are asking for a simple default sort for the type you're soring, then I'd use the delegate.

Here's the whole console app I used to experiment with this stuff. The example starts with a simple Car class designed with a few features I like to use for experimenting; built-in sample data, a ToString override and a print method. I've included various sorts, some wacky some traditional; you might dream up some of your own. You know your clients will. Main is just a bunch of different calls to Sort, using various approaches. Everything is here so it's a little hard to see eactly what's being used when, like you might wonder, "When is the Comparer.Compare method in use as opposed to the IComparable.CompareTo method. You can comment stuff out of copy bits and pieces into new console apps to isolate just the parts you want. Learning is all about experimenting, so copy & paste it and CHANGE it. I didn't know any of this stuff when I started this article a few days ago. Nothing like practice to nail down a concept.

Add your comment: