Professor Mustard Programming
 

Programming 101 - Unit 06 - Other Features

06i) Sorting Data
  
When dealing with arrays, a common need is sorting the array's elements by a certain metric. For example, you may want to sort a list of employees by name, or a list of tasks in order of priority. There are several ways that this can be accomplished, so let's start with the simplest: sorting an array of basic datatypes (for our purposes, all the collections in today's lesson will be ArrayLists).

If we have an array of strings, ints, floats or some other primitive datatype, then sorting them couldn't be simpler. We just make the following call:

myArray.Sort();


...and, poof! The array's elements will be re-ordered in ascending order. The lowest values, like "A" or 5, filter to the top, while the highest values, like "Z" or 10000, filter to the bottom. However, it gets a little trickier when we want to sort an array of objects that we've defined ourselves. Say that you've written an "Employee" class, for example. How in blazes is C# supposed to know if one Employee is "greater than" or "less than" another Employee? Salary? Performance? Number of relatives in upper management? C# can't really assume how we're comparing Employee objects, so we have to do it ourselves. The simplest way is to make your class inherit the "IComparable" interface, and then write a CompareTo() method for it, like so:

class Employee: IComparable
{
  public string Name;
  public double Salary;

  public int CompareTo(object obj)
  {
    if( obj is Employee )
    {
      Employee otherEmployee = (Employee)obj;
      return this.Name.CompareTo(otherEmployee.Name);
    }
    else
    {
      return 0;
    }
  }
}


In C#, any method for comparing two objects has three valid return values. -1 means that the first object is less than the second object, 1 means that the first object is greater than the second object, and 0 means that they are equal. In the case of our CompareTo() method above, the "first object" is the actual Employee instance containing the method, and the "second object" is the parameter "obj".

In this example, we've assumed that we always want to compare Employees by alphabetical order of their name. And since the "name" property is just a simple string, comparing a name is as simple as calling its CompareTo() method, which will return the -1, 0 or 1 that we can pass back as the return value of our method. Note that, before performing the compare, we check to make sure that the comparison object is also an Employee. What should you do if it isn't? Well, you could just return a 0, which means that the objects are equivalent, and thus there will be no movement in the array. You could also throw an exception, if it's important to ensure that the programmer can't compare Employee objects to CombustionEngine objects, or whatever.

The beauty of the CompareTo() method is that it provides a default comparison metric for our class to use. So, if our array is full of Employee objects, and we call the array's "Sort()" method, the array will reorder itself by Employee name, just as we've told it to in the Employee's CompareTo() method. Note that we never directly call the CompareTo() method on an Employee object, either... we simply call the array's Sort() method, and let C# make all the CompareTo() calls for us. That's pretty slick!

Still, what if we want to order them some other way? By salary, for example, or descending instead of ascending? If we want the ability to sort Employees in several different ways, the CompareTo() method just isn't going to cut it. Fortunately, C# has another interface, IComparer, that fills this very need. It allows us to create an unbounded number of specialized classes, used exclusively for sorting. Let's look at one now:

public class EmployeeSalaryComparer : IComparer
{
  public int Compare(object obj1, object obj2)
  {
    if( obj1 is Employee && obj2 is Employee )
    {
      Employee emp1 = (Employee)obj1;
      Employee emp2 = (Employee)obj2;

      return emp1.Salary.CompareTo(emp2.Salary);
    }
    else
    {
      throw new ArgumentException("Both objects must be of type Employee!");
    }
  }
}


The above class can be used to sort an array of Employee objects, by salary. To use it, we simply create an instance of it, and then pass that instance into our array's Sort() call:

EmployeeSalaryComparer comparer = new EmployeeSalaryComparer();
myArray.Sort(comparer);


This tells our program to use the Compare() method in EmployeeSalaryComparer for sorting our objects, instead of using the default CompareTo() logic in the objects that are being sorted. If we wanted to sort by some other metric, we'd simply create another IComparer class which used that metric instead. So, there are no limits to the number of sorting operations we can define!

What if we want a comparison method that sorts by descending, instead of ascending? We simply reverse the order in which the two objects are compared:

// emp2 is listed first
return emp2.Salary.CompareTo(emp1.Salary);


What if we want a comparison method that sorts by one metric, and then another? For example, we want to sort by salary, but we want all the employees with the same salary to be grouped alphabetically, by name? We just check for 0 after the first compare (which means the values were the same), and then perform a second compare based on our other value:

int result = emp1.Salary.CompareTo(emp2.Salary);

if( result == 0 )
{
  return emp1.Name.CompareTo(emp2.Name);
}

return result;


Now, suppose that you're trying to sort an array of a classes with like, 300 properties, and you don't feel like writing an IComparer class for every last one. Well, in this case, you can use a wonderful tool called "Reflection" to write an IComparer that sorts by any property you specify! Observe:

public class AdvancedEmployeeComparer : IComparer
{
  private string _compareProperty;
  public string CompareProperty { get{ return _compareProperty; } }

  public AdvancedEmployeeComparer(string compareProperty)
  {
    _compareProperty = compareProperty;
  }

  public int Compare(object obj1, object obj2)
  {
    PropertyInfo prop1 = obj1.GetType().GetProperty(_compareProperty);
    PropertyInfo prop2 = obj2.GetType().GetProperty(_compareProperty);

    object[] index = null; // ...and don't worry about this guy
    IComparable val1 = (IComparable)prop1.GetValue(obj1, index);
    IComparable val2 = (IComparable)prop2.GetValue(obj2, index);

    return val1.CompareTo(val2);
  }
}


You don't have to fully understand all that stuff that before the comparison call; just know that we're looking up a specific property in both objects, the name of which is supplied in "_compareProperty". If we wanted this beast to sort by Name, for example, the call would look like this:

AdvancedEmployeeComparer comparer = new AdvancedEmployeeComparer("Name");
myArray.Sort(comparer);


That's right. We can just pass a string containing the name of the desired property, and our comparer class will actually look up that property and compare it for us. As long as a valid property name is provided, and the property's datatype is sortable, it works perfectly (if either of those conditions are false, it might throw an exception). Note, too, that there's no mention of Employee in that class. Because everything happens at an extremely abstract level, you could technically use that class to compare any property of any class you wanted! Now that is slick. Naturally, if you wanted to use the "AdvancedEmployeeComparer" for that purpose, you should rename it to just "AdvancedComparer" first, so that people won't think it's only for Employee objects. Also, before you get too excited about reverse-engineering that class and never writing an IComparer class again, please bear in mind that Reflection is a tad slow. It will never run as fast as an IComparer that is hard-coded to work a certain way (but if you don't care, be my guest and reuse it however you want)!

We could make this class even more sophisticated by allowing you to pass in more than one property name (so that you could sort by one property, then another), or by letting you specify ascending or descending sort order. In fact, some of this will be covered in the code sample below. Enjoy.



// Remember the return codes in a "Compare" method:
// -1 means that the first object is "less than" the second object
// 0 means that the first object is "equal to" the second object
// 1 means that the first object is "greater than" the second object

using System;
using System.Collections; // needed for ArrayList
using System.Reflection; // only needed for advanced comparer

namespace I_Comparing
{
  class Class1
  {
    static readonly string ln = Environment.NewLine;

    [STAThread]
    static void Main(string[] args)
    {
      // Create an ArrayList with some Employees
      ArrayList emps = new ArrayList();
      emps.Add(new Employee("Zeke Smith", 15.00));
      emps.Add(new Employee("Gary Miller", 20.00));
      emps.Add(new Employee("Robin Baker", 18.00));
      emps.Add(new Employee("Will Smith", 200.00));
      emps.Add(new Employee("Zeke Smith", 16.00));

      // Show the array's contents prior to sorting
      Console.WriteLine("Array before sort: ");
      PrintEmpArray(emps);

      // Sort the array, using each element's
      // "CompareTo()" method to determine order.
      emps.Sort();
      Console.WriteLine(ln + "Array after default sort: ");
      PrintEmpArray(emps);

      // Sort the array, using our simple
      // "Comparer" class:
      SimpleEmployeeComparer simpComparer = new SimpleEmployeeComparer();
      emps.Sort(simpComparer);
      Console.WriteLine(ln + "Array after simple sort: ");
      PrintEmpArray(emps);

      // Sort the array, using our complex
      // "Comparer" class:
      AdvancedEmployeeComparer advComparer = new AdvancedEmployeeComparer("Salary", false);
      emps.Sort(advComparer);
      Console.WriteLine(ln + "Array after advanced sort: ");
      PrintEmpArray(emps);
      
      PromptForExit();
    }

    static void PrintEmpArray(ArrayList emps)
    {
      for(int i = 0; i < emps.Count; ++i)
      {
        Employee emp = (Employee)emps[i];
        string printString = "[" + i.ToString() + "]: ";
        printString += "Name=\"" + emp.Name + "\" ";
        printString += "Salary=" + emp.Salary.ToString() + "";
        Console.WriteLine(printString);
      }

    }

    static void PromptForExit()
    {
      Console.Write(ln + "Program complete! Hit enter to exit...");
      Console.ReadLine();
    }
  }

  // Example of an intrinsically comparable class
  // Note that it inherits the IComparable interface
  class Employee: IComparable
  {
    private string _name;
    private double _salary;
    public string Name { get{ return _name; } }
    public double Salary { get{ return _salary; } }

    public Employee(string name, double salary)
    {
      _name = name;
      _salary = salary;
    }
    
    public int CompareTo(object obj)
    {
      if( obj is Employee )
      {
        // Return the result comparing of this Employee's Name
        // against the other Employee's name
        Employee otherEmployee = (Employee)obj;
        return this.Name.CompareTo(otherEmployee.Name);
      }
      else
      {
        // Just return "0" when someone tries to compare this Employee object
        // against a non-employee object, so that there's no movement. Unless,
        // of course, you actually WANT all Employee objects to filter to the
        // top or bottom of an object collection. You could also throw an
        // exception if you prefer; it's totally up to you.
        return 0;
      }
    }
  }

  // This is a simple "Comparer" class
  // We'll make it slightly "brainier" than the default comparer in
  // the Employee class. This one will sort by name, and THEN by salary.
  public class SimpleEmployeeComparer : IComparer
  {
    public int Compare(object obj1, object obj2)
    {
      if( obj1 is Employee && obj2 is Employee )
      {
        Employee emp1 = (Employee)obj1;
        Employee emp2 = (Employee)obj2;

        int result = emp1.Name.CompareTo(emp2.Name);

        // If the result of the first compare is 0, then the
        // names are the same. We'll compare again, this time
        // by salary. You could repeat this process for as many
        // "levels" of comparison as you wanted.
        if( result == 0 )
        {
          return emp1.Salary.CompareTo(emp2.Salary);
        }

        return result;
      }
      else
      {
        throw new ArgumentException("Both objects must be of type Employee!");
      }
    }
  }

  // This comparer adds the ability to sort either ascending or descending.
  // It also lets the user specifiy which property to use for comparing.
  // You could go as far with this as you wanted, even allowing for multiple
  // levels of comparison to be specified.
  public class AdvancedEmployeeComparer : IComparer
  {
    private string _compareProperty;
    private bool _ascending; // this would be nicer as an enum

    public string CompareProperty { get{ return _compareProperty; } }
    public bool Ascending { get{ return _ascending; } }

    public AdvancedEmployeeComparer(string compareProperty, bool ascending)
    {
      _compareProperty = compareProperty;
      _ascending = ascending;
    }

    public int Compare(object obj1, object obj2)
    {
      try
      {
        // Get PropertyInfo for each object, based on the name you
        // provided the constructor.
        PropertyInfo prop1 = obj1.GetType().GetProperty(_compareProperty);
        PropertyInfo prop2 = obj2.GetType().GetProperty(_compareProperty);

        // Get the value of each property. We don't care about the
        // underlying datatype, we just care that they're comparable.
        object[] index = null; // ...and don't worry about this guy
        IComparable val1 = (IComparable)prop1.GetValue(obj1, index);
        IComparable val2 = (IComparable)prop2.GetValue(obj2, index);

        // The issue of "ascending" vs "descending" is a simple matter
        // of reversing the order in which the objects are compared.
        if( _ascending )
          return val1.CompareTo(val2);
        else
          return val2.CompareTo(val1);
      }
      catch (Exception ex)
      {
        throw new ArgumentException("CompareTo is not possible: " + ex.Message);
      }
    }
  }
}