Sorting Custom Arrays in C#...

This article explains the various mechanisms available for sorting arrays in .Net and specifically how to sort custom arrays using the IComparer interface.

By: Nitin Pande Date: January 31, 2005 Download the code.

The .NET platform provides rich facilities for sorting and searching arrays. The sorting operation is the most common operation performed by programmers and with C# it is all the more easier to write sorting procedures do to the built in capabilities of the .net framework that not only reduce the development time but also provide efficient sorting techniques. However it is important to understand the usage of the sorting mechanism available in .net to take their advantage in the best possible way instead of reinventing the wheel.

Arrays in C#

In C#, an array index starts at zero. That means first item of an array will be stored at 0th position. The position of the last item on an array will total number of items – 1.

In C#, arrays can be declared as fixed length or dynamic. Fixed length array can stores a predefined number of items, while size of dynamic arrays increases as you add new items to the array. You can declare an array of fixed length or dynamic. You can even change a dynamic array to static after it is defined. For example, the following like declares a dynamic array of integers.

int [] intArray;

The following code declares an array, which can store 5 items starting from index 0 to 4.

int [] intArray; intArray = new int[5];

The following code declares an array that can store 100 items starting from index 0 to 99.

int [] intArray; intArray = new int[100];

Dynamic arrays in C#

VB or VB.Net programmers generally face the difficulty of not being able to use dynamic arrays in C# as easily as they did in VB. The reason for this is very simple, C# does not provide a mechanism to preserve the items of the array when it is re dimensionised!!! There is no "ReDim Preserve" available in C#. So you can use this simple piece of code to increase the size of your array dynamically.

public String[] GrowArray(String[] pOldArray, Int32 pNewSize)
{
  Int32 counter = 0;
  String[] newArray = null;

  if(pOldArray != null)
  {
    if(pNewSize <= pOldArray.Length)
    {
      newArray = pOldArray;
    }
    else
    {
      newArray = new String[pNewSize];
      foreach(String item in pOldArray)
      {
        newArray[counter] = item;
        counter++;
      }
    }
  }
  //all the items of the old array have been copied to the new array and the new items are NULL
  return newArray;
}

A work around to this situation that is generally used, is to use an ArrayList instead of an Array. The advantage of using an ArrayList is that you can add items to it without losing the previous values. The following code snippet shows the use to an ArrayList to dynamically add items to a String array.

public String[] AddToArray(String[] pOldArray, String pNewItem)
{
  ArrayList originalList = new ArrayList(pOldArray);
  originalList.Add(pNewItem);
  return(String[])originalList.ToArray(typeof(String));
}

The last line of the code returns a String array from the function, by type casting the Arraylist to a String type array. A common mistake made by most programmers new to C# is that they do not provide the typeof parameter to the ToArray method of the ArrayList. The typeof keyword instructs the C# compiler to convert the array elements to the given type.

Sorting of Arrays:

To sort a simplest 1 dimensional array in alphabetical order, we'll leverage the static "Sort" method in the Array class to sort the array. The Array.Sort method will sort the array in place, meaning we don't have to create another array to contain the resulting array. Here is how:

String[] myArray = {"Zebra","Ant","Owl","Lion"};
Array.Sort(myArray);

This will result in the array getting sorted in the ascending order i.e. iterating the elements of this array will cause the output in the following manner:

Ant
Lion
Owl
Zebra

Code Snippet

[STAThread]
static void Main(string[] args)
{
  String[] myArray = {"Zebra","Ant","Owl","Lion"};
  Array.Sort(myArray);
  foreach(String item in myArray)
  {
    Console.WriteLine(item);
  }
  Console.ReadLine();
}

Another overloaded implementation of Sort method is used to sort two arrays whose elements can work as Key Value pairs. Consider two arrays Animals and Places, now you need to sort these arrays, but at the same time do not want to disturb the mapping between each item of the “Animals” array and that of the corresponding element in the "Places" array. In this case we can pass both arrays as parameters to the sort method that does the needful. Here is the code snippet:

String[] animals = {"Zebra","Kiwi","Amazona Parrot","Tiger"};
String[] places = {"Africa","New Zealand","Jamaica","India"};
Array.Sort(animals,places);
foreach(String item in animals)
{
  Console.WriteLine(item);
}
Console.WriteLine();
foreach(String item in places)
{
  Console.WriteLine(item);
}

The output of this code is given below:

Amazona Parrot
Kiwi
Tiger
Zebra

Jamaica
New Zealand
India
Africa

As you can see, the "animals" array has been sorted in the ascending order but the array "places" has been sorted with respect to the elements of the "animal" array.

Sorting arrays of custom types

After having seen the use of the simple but powerful Sort method of the Array class in sorting the arrays of the system defined data types, let us tackle the problem of sorting the array of custom types. Most complex business applications require complex classes or custom business objects to be created to contain data that will be used by the application. In such a scenario if we have an array of a custom type and want to sort it, simply passing the array to the Sort method will not work. Try this piece of code and see what happens:

First create a class TestClass with a property FirstName.

public class TestClass
{
  private String firstName;

  public TestClass()
  {
    //
    // TODO: Add constructor logic here
    //
  }

  public String FirstName
  {
    get
    {
      return firstName;
    }
    set
    {
      firstName = value;
    }
  }
}

Now in the main method of your console application write the following code:

TestClass[] items = new TestClass[4];

items[0] = new TestClass();
items[0].FirstName = "John";

items[1] = new TestClass();
items[1].FirstName = "Kim";

items[2] = new TestClass();
items[2].FirstName = "Robin";

items[3] = new TestClass();
items[3].FirstName = "Peter";

Array.Sort(items);

Running the program causes the following runtime exception to occur.

Specified IComparer threw an exception.

What does this suggest? This means that the array of custom data types cannot be sorted just by passing the array to the Sort method of the Array class and why not?? We cannot expect the creators of .Net platform to know about all the objects that we may create for our purpose and write compare and sorting routines for them!!! But that is not all, there is another hint hidden in the error that we have received and that is by default .Net expects all custom classes that need to be sorted to implement the IComparer interface.

You would be wondering that what is the IComparer all about and I would tell you that it is another example of the flexibility and beauty of the .Net platform. We know that when we write custom classes we may need to compare and sort the arrays of those classes. We also know that the Sort method cannot be used for reasons explained above and to overcome this limitation MS can exposed the IComparer and IComparable interfaces both of which contain the Compare method.

If our custom classes override this Compare method we can write accurate comparison routines for our objects. Once we have implemented that, we can pass the array of objects to the Sort method as before and viola the array gets sorted!! This is because when the Sort method is passed the array of custom objects it uses the Compare method to compare each object and then sort it.

Before I discuss a complete example using the IComparer and IComparable let me focus on one more aspect of OOPS as used here and that is the use of Interfaces. Why have the creators of .Net exposed the comparison of custom objects as Interfaces and not abstract classes? The answer again lies in the principle of OOPS. When you want to write a class whose objects will need to be sorted then it is a must for the programmer to override the method Compare, (after all the Compare method is used by the Sort method of Array class to applying sorting on the array) hence it is declared in an interface because the moment you implement an interface, you have to override all it methods compulsorily and that's how the .Net guys have ensured that sorting for any kind of custom objects can be easily implemented without leaving any scope for buggy weak code.

So far we have learnt that in order to prepare custom classes that can be sorted in an array, the classes have to implement either of the two interfaces IComparer or IComparable and override the Compare method. The following table lists the difference between the two interfaces:

IComparableIComparer
Comparing method must be defined within the class for which it is used. Comparing method is defined in a separate class.
Can provide only one method for which to compare objects of the class. Many classes can be defined, each class can contain a distinct comparing method.
Because it is defined within the class, it can access private variables on which to sort. Can only sort on public properties and fields.
If both interfaces are defined for sorting, this one is not used. If both interfaces are defined for sorting, this one is used.
Provides an alternative sorting method for the class for which it is used. Provides a default comparing method for the class in which it is defined.

Let us now discuss the implementation the IComparer interface.

We will create a custom class that will represent first name, last name and salary for an employee. Then we will sort the array of objects of this class using the IComparer interface and also specify the field on which the sorting will be applied i.e. either by first name, last name or by salary. In my example I have chosen the sorting to be applied on all the fields one by one.

Here goes the code snippet for the custom class:

namespace Example_Icomparer
{

  #region Public Variables
  public enum CompareField
  {
    FirstName,
    LastName,
    Salary
  }
  #endregion

  /// <summary>
  /// Class MyClass demonstrates the sorting of an array of custom objects using IComparer interface
  /// </summary>
  class MyClass
  {

    #region Private Variables
    private String fName;
    private String lName;
    private Double salary;
    #endregion

    #region Property
    public String FirstName
    {
      get
      {
        return fName;
      }
      set
      {
        fName = value;
      }
    }

    public String LastName
    {
      get
      {
        return lName;
      }
      set
      {
        lName = value;
      }
    }

    public Double Salary
    {
      get
      {
        return salary ;
      }
      set
      {
        salary = value;
      }
    }

    #endregion

    /// <summary>
    /// The main entry point for the application.
    /// </summary>
    [STAThread]
    static void Main(string[] args)
    {
      //
      // TODO: Add code to start application here
      //
      CompareClass compareType;

      compareType = new CompareClass(CompareField.FirstName);
      Console.WriteLine("Demo Sorting by first name:");
      MyClass.SortObjects(compareType,true);

      compareType = new CompareClass(CompareField.LastName);
      Console.WriteLine("Demo Sorting by last name:");
      MyClass.SortObjects(compareType,true);

      compareType = new CompareClass(CompareField.Salary);
      Console.WriteLine("Demo Sorting by salary:");
      MyClass.SortObjects(compareType,true);

    }

    #region Methods
    private static void SortObjects(CompareClass pSortBy, Boolean pSortAscending)
    {
      Int32 index = 0;

      MyClass[] items = new MyClass[4];
      //---
      items[0] = new MyClass();
      items[0].fName = "Zelna";
      items[0].lName = "Huber";
      items[0].salary = 300;
      //---
      items[1] = new MyClass();
      items[1].fName = "Nathan";
      items[1].lName = "Astle";
      items[1].salary = 400;
      //---
      items[2] = new MyClass();
      items[2].fName = "Peter";
      items[2].lName = "Moore";
      items[2].salary = 100;
      //---
      items[3] = new MyClass();
      items[3].fName = "Amy";
      items[3].lName = "Rice";
      items[3].salary = 200;

      Console.WriteLine("Before Sorting:");
      foreach(MyClass item in items)
      {
        Console.WriteLine("S.No: {0} :: First Name: {1} :: Last Name: {2} :: Salary: {3}",index.ToString(),item.FirstName, item.LastName, item.Salary);
        index ++;
      }
      Console.WriteLine();
      Console.ReadLine();

      Array.Sort(items,pSortBy);
      if(!pSortAscending)Array.Reverse(items);
        index = 0;
      Console.WriteLine("After Sorting:");
      foreach(MyClass item in items)
      {
        Console.WriteLine("S.No: {0} :: First Name: {1} :: Last Name: {2} :: Salary: {3}",index.ToString(),item.FirstName, item.LastName, item.Salary);
        index ++;
      }
      Console.WriteLine();
      Console.ReadLine();

    }

    #endregion
  } //end of class
} //end of namespace

Explanation

At the top of the code, we can see the declaration of an enumeration CompareField that specifies the field using which the sorting will be applied. The class MyClass contains the data members fName, lName and salary. It has only one method SortObjects that contains the two parameters. One, the object of the class that implements the IComparer interface (CompareClass pSortBy) and second, a Boolean flag indicating ascending sort or otherwise.

The Main method of the class creates an instance of the CompareClass by passing the sorting field as parameter. It then calls the SortObjects method that creates the array of MyClass objects and sorts them by calling the Sort() method of the Array class. The difference in this call is the additional object of the class that implements Compare method of the IComparer interface.

Let us now take a look at the code of the CompareClass

namespace Example_Icomparer
{
  /// <summary>
  /// The CompareClass provides the implementation of the IComparer inteface
  /// </summary>
  class CompareClass : IComparer
  {
    #region Private Variables
    private CompareField sortBy = CompareField.FirstName;
    #endregion

    #region Properties
    public CompareField SortBy
    {
      get
      {
        return sortBy;
      }
      set
      {
        sortBy = value;
      }
    }
    #endregion

    #region Constructor

    public CompareClass()
    {
      //default constructor
    }

    public CompareClass(CompareField pSortBy)
    {
      sortBy = pSortBy;
    }

    #endregion

    #region Methods
    public Int32 Compare(Object pFirstObject, Object pObjectToCompare)
    {
      if(pFirstObject is MyClass)
      {
        switch(this.sortBy)
        {
          case CompareField.FirstName:
            return String.Compare(((MyClass)pFirstObject).FirstName,((MyClass)pObjectToCompare).FirstName);
            break;
          case CompareField.LastName:
            return String.Compare(((MyClass)pFirstObject).LastName,((MyClass)pObjectToCompare).LastName);
            break;
          case CompareField.Salary:
            return Comparer.DefaultInvariant.Compare(((MyClass)pFirstObject).Salary,((MyClass)pObjectToCompare).Salary);
            break;
          default:
            return 0;
            break;
        }
      }
      else
        return 0;
    }
  }
  #endregion
}

Explanation

The CompareClass is the actual class responsible for the sorting of the array of custom objects. This is a user-defined class that implements the IComparer interface. For the sake of our example I have maintained only one property i.e. SortBy which is of the type CompareField – the enumeration declared first in the namespace.

This class provides the concrete implementation for the Compare method declared in the IComparer interface. Take a look at the code snippet again:

    public Int32 Compare(Object pFirstObject, Object pObjectToCompare)
    {
      if(pFirstObject is MyClass)
      {
        switch(this.sortBy)
        {
          case CompareField.FirstName:
            return String.Compare(((MyClass)pFirstObject).FirstName,((MyClass)pObjectToCompare).FirstName);
            break;
          case CompareField.LastName:
            return String.Compare(((MyClass)pFirstObject).LastName,((MyClass)pObjectToCompare).LastName);
            break;
          case CompareField.Salary:
            return Comparer.DefaultInvariant.Compare(((MyClass)pFirstObject).Salary,((MyClass)pObjectToCompare).Salary);
            break;
          default:
            return 0;
            break;
        }
      }
      else
        return 0;
    }

What goes on inside is that when you call the Array.Sort() method, and pass the object of the class that implements the IComparer interface, it automatically searches for the Compare method implemented in that class (in our case CompareClass) and executes the same.

That’s It!! This is all you need to implement sorting on an array of Custom objects.

You may download the code here.