Multi-Level Sorting in .NET

A common, classic problem in computer science is to sort a collection (such as an array or a List) of objects which have multiple fields. For example, suppose you have an Employee object which has a job Title field (which can be either “President”, “Manager”, or “Worker”), a LastName field (such as “Smith”), and an Age field (such as 32). In .NET this is easily done using IComparable and best explained by example.

Suppose our preliminary thought for an Employee class is:

public class Employee
{
  public string title;
  public string lastName;
  public int age;
. . . etc.

To enable ascending sorting from low to high we can implement the IComparable interface like so:

public class Employee : IComparable<Employee>
{
  public string title;
  public string lastName;
  public int age;

  public Employee(string title, string lastName, int age)
  {
    this.title = title;
    this.lastName = lastName;
    this.age = age;
  }

  public int CompareTo(Employee otherEmp)
  {
    // only one way two Employee can be equal (0)
    if (String.Compare(this.title, otherEmp.title) == 0 &&
     String.Compare(this.lastName, otherEmp.lastName) ==  0 &&
     this.age == otherEmp.age)
    return 0;

    // this > other (1) based only on title
    if (this.title == “President” &&
     otherEmp.title != “President”)
    return 1;
    else if (this.title == “Manager” &&
     otherEmp.title == “Worker”)
    return 1;
     
    // this > other where titles equal but last names different
    if (String.Compare(this.title, otherEmp.title) == 0 &&
     String.Compare(this.lastName, otherEmp.lastName) == 1)
    return 1;

    // this > other where titles and names equal, ages different
    if (String.Compare(this.title, otherEmp.title) == 0 &&
     String.Compare(this.lastName, otherEmp.lastName) == 0  &&
     this.age > otherEmp.age)
    return 1;

      return -1; // all possibilities except < examined
    }

    public override string ToString()
    {
      return this.title + “, ” + this.lastName + “, ” + this.age;
    }

  }

Using the new ordering CompareTo method to sort a list of Employee objects from low to high could look like this:

List<Employee> list = new List<Employee>();
list.Add(new Employee(“President”, “Smith”, 58));
list.Add(new Employee(“Manager”, “Brown”, 33));
list.Add(new Employee(“President”, “Jones”, 58));
list.Add(new Employee(“Worker”, “Green”, 28));
       
list.Sort();
for (int i = 0; i < list.Count; ++i)
{
  Console.WriteLine(i + ” ” + list[i].ToString());
}

The Sort() method will automatically use the ordering defined by the Employee CompareTo method. In CompareTo we first check to see if two Employee objects are equal and if so return 0 (the required code for equality). This can only happen when the titles, last names, and ages are all equal. Note the String.Compare rather than == for the lastName. Next we check for when the this Employee is greater than the otherEmp and if so return the required +1 code. This can happen based only on title, or if titles are equal, on last name, or if both titles and last names are equal, on age. Here we assume that President > Manager > Worker. I could have written a helper function for this comparison instead of coding directly. After all these checks there’s only one possibility left, and that is that the this Employee is less than (code -1) than the other Employee. You can use this pattern in general: check for equality, then check for conditions where this > other, and then the only case left is this < other.

The ideas are simple but it’s easy to mess up the details checking for this > other.

Now this example defines a single (ascending) sort order. If you want multiple ways to sort, typically ascending and descending, you can implement the IComparer interface as a class and then pass the class into Sort(). Briefly (omitting lots of details),

public class SortDescending : IComparer
{
  public int Compare(Employee a, Employee b) { . . . }
}

public class SortAscending : IComparer
{
  public int Compare(Employee a, Employee b) { . . . }
}

and then call like

list.Sort(new Employee.SortDescending());

You can see the MSDN Library for details.

This entry was posted in Software Test Automation. Bookmark the permalink.