Generic Sorting
page 1 of 1
Published: 03 Jun 2004
Unedited - Community Contributed
Abstract
Write that sort code once and for all. Harness the power of reflection to easily genericise your sort logic to work on any properties with multiple levels and differing orders.
by Jonathan Cogley
Feedback
Average Rating: This article has not yet been rated.
Views (Total / Last 10 Days): 10310/ 23

[Download Binary]
[Download Source Project with Unit Tests]

Let's be honest - writing sorting code ranks right up there with client side script validation! - tedious, boring, horrible code that gets in the way of doing more interesting things.  It is repetitive and predictable.  This article will introduce a way to use one "sorter" for all your sorting requirements, amen.

Reflection is a wonderful technology which has been implemented through a powerful yet easy to use API in the Microsoft .NET Framework.  The basic idea is to use code to look back at objects, methods, properties and other parts of your code. See the System.Reflection namespace documentation for more details.

The Basics of Sorting

The .NET framework already provides the general purpose QuickSort algorithm for sorting in the form of the System.Collections.ArrayList.Sort and System.Array.Sort methods which allow for sorting an ArrayList and an Array respectively.  That takes care of the algorithm, but what about the individual evaluation as the elements are compared?  How do those algorithm implementations do their evaluation?  They use the System.IComparable interface which takes the object to be compared to and returns an integer result.  The basic types all implement System.IComparable such as int, string, DateTime, etc.

How do you get these algorithms to sort your own custom objects?  There are overloads on the Sort methods which take a System.Collections.IComparer.  This is an interface which can be implemented to provide your own custom evaluation of two objects.  Since the Microsoft Design Guidelines indicates that properties should be used to represent available information on objects then it is logical to think that your sort should be able to order your objects by their properties.

Sorting Custom Objects

The Thycotic.Collections.dll provides this exact functionality.  It provides a PropertyComparer implementation of IComparer that allows you to sort your Array or ArrayList using one or more properties in ascending or descending order.

 
using Thycotic.Collections;

Pet[] pets = new Pet[4]; 
Pet pet1 = new Dog("Indiana", 3); 
Pet pet2 = new Dog("Rajiv", 3); 
Pet pet3 = new Dog("Chewey", 5); 
Pet pet4 = new Dog("Indiana", 5); 
pets[0] = pet1; 
pets[1] = pet2; 
pets[2] = pet3; 
pets[3] = pet4; 

PropertyComparer comparer = new PropertyComparer(); 
comparer.AddPropertyName("Name", CompareOrder.Ascending); 
comparer.AddPropertyName("Age", CompareOrder.Descending); 

Array.Sort(pets,comparer); 

The simple code snippet above creates an array of Pets (specifically Dogs) and then sorts them by their Name property ascending and the Age descending.  The PropertyComparer has no prior knowledge of the Pet class and does not need to since it uses Reflection to access the properties.

How to get and use the PropertyComparer

  • Download Thycotic.Collections.dll from link at the top of this article
  • Add a reference to the Thycotic.Collections.dll for your project

What features does Thycotic.Collections have?

  • Free
  • Open source (LGPL)
  • Sort any objects using any properties in any order
  • Sorts arrays/collections containing nulls
  • Sorts by properties whose value is null
  • Sorts on properties when some objects may not have the property
  • Fully Test Driven code with complete unit tests

Performance

Using Reflection has associated costs.  This has always been the case since late binding is not as efficient as early binding.  Included in the source project is a performance unit test fixture that sorts by one and then two properties, first using the PropertyComparer and then using a single purpose comparer.  The difference in performance is surprising!  Due to the nature of the QuickSort algorithm the evaluations must occur many times causing the Reflection penalty to be paid over and over again.  By adding some simple caching of instance property values, I was able to improve the performance of the PropertyComparer by 60-70%.  The cached version was still 25-50x slower than an early bound version. 

Performance Chart

The top 3 bars are sorting on 2 properties - 1) early bound, 2) PropertyComparer with caching, 3) PropertyComparer without caching

The bottom 3 are sorting on 1 property - 1) early bound, 2) Property Comparer with caching, 3) PropertyComparer without caching 

It is unlikely that performance will be an issue unless your sort is an intensively used part of your application and your application routinely experiences very heavy load - of course the decision is a trade off between convenience and performance.

Conclusion

I first used this concept in Java and it was one of the first things I ported over to .NET and I have used it many .NET applications since.  It has also served as my example project while presenting Test Driven Development at various .NET User Groups.  After much spurring from other developers (most notably Steven Smith a while back) and a deep sense of guilt, I have finally come around to sharing this time saver with others.  I hope it will be as useful to you as it has been to me.

Feel free to peruse the source code and submit any bugs, enhancements or comments.  Please rate this article.



User Comments

Title: Senior Systems Analyst   
Name: Paul Atkinson
Date: 2006-02-08 7:25:03 PM
Comment:
I've been using thycotic collections and noticed it seems to sort English (e.g. E) and French (e.g. É) strings equally. How are you doing this?
Title: Hello   
Name: World
Date: 2005-10-06 12:01:05 PM
Comment:
This is some excellent code. Thanks.
Title: Properties inside properties   
Name: Age
Date: 2005-08-31 9:52:45 AM
Comment:
I don't think it should be too difficult, I'm a bit busy at the mo' but I'll take a look sometime this week or next. I'll let you know how I get on.

cheers
Title: Reply to "Properties inside properties"   
Name: Jonathan Cogley
Date: 2005-08-30 1:34:17 PM
Comment:
The current implementation does not support properties inside properties however you could adapt it to do so. I have not had a need for such functionality in any applications to date.

The trick might be where to stop then ... what about methods? Often a sub-object may be returned from a method not a property and you could continue to do this through reflection. Before you know it, you may be writing another DataBinder.Eval type method or some other code-parsing engine. Drop me a line if you try anything with this approach.

Best regards,
Jonathan Cogley
Title: Properties inside properties   
Name: Age
Date: 2005-08-30 1:20:29 PM
Comment:
This looks great. However, do you know if you can sort on a property within a property.
For example
pet = new GetPets()
comparer.AddPropertyName("Teeth.Size", Ascending);
comparer.AddPropertyName("Age", Ascending);
Array.Sort(pets,comparer);
Title: Reply to John   
Name: Jonathan Cogley
Date: 2005-06-06 9:30:26 PM
Comment:
John, in response to your comment above ...

This module implements IComparer so it is really designed for comparing objects in a sort algorithm. You could take the idea of late binding properties and apply it to a search algorithm but it would be a little different. You may want to consider simply doing the search in SQL or using the Filter method on a DataTable.

If you do port the code over to use for searching, I would be most interested in hearing about your experiences.

Regards,
Jonathan
Title: Thanks   
Name: BG
Date: 2005-06-06 3:05:03 PM
Comment:
Works great...thanks much!
Title: Mr   
Name: John
Date: 2005-02-08 11:43:42 AM
Comment:
Can this module be adapted to return a filtered collection of objects. I'd like to see a function that would take in the field name and a search value and return all the objects whose field matches that value.






Community Advice: ASP | SQL | XML | Regular Expressions | Windows


©Copyright 1998-2024 ASPAlliance.com  |  Page Processed at 2024-10-15 6:43:14 AM  AspAlliance Recent Articles RSS Feed
About ASPAlliance | Newsgroups | Advertise | Authors | Email Lists | Feedback | Link To Us | Privacy | Search