4.11 Sorting Collections

You want to sort the items in a collection.

Technique

The Array class contains a static Sort method. There are several overloaded versions of this method. To simply sort an array, pass the array as a parameter. If you need to sort a dictionary-based collection, create two arrays by converting the Keys and Values collections. Pass these two arrays into the Sort method. It will sort the Keys array and place each value associated with each key at the same index within the Values array. The additional Sort methods allow you to sort a range of items within the array.

The ArrayList contains three overloaded Sort methods. This nonstatic method works on a current instance of an ArrayList object. It too allows you to sort the array or a smaller range of items within the array.

The Array and ArrayList Sort methods also allow you to define your own comparison method. Create a class or struct that implements the IComparer interface. This interface contains one method, Compare , which accepts two objects as parameters. It returns an integer less than 0 if the first object is less than the second object, an integer greater than 0 if the first object is greater, and 0 if the two objects are the same:

 struct Person : IComparer {     public string firstName;     public string lastName;     // a Person is identified by a first and last name     public Person( string first, string last )     {         firstName = first;         lastName = last;     }     // compares 2 Person objects     public int Compare( object a, object b )     {         int lNameCmp;         int fNameCmp;         Person pa = (Person) a;         Person pb = (Person) b;         // compare last names first         lNameCmp = String.Compare( pa.lastName, pb.lastName );         // if names are not equal, return the result         if( lNameCmp != 0 ) return lNameCmp;         // last names were equal, check the first names         fNameCmp = String.Compare( pa.firstName, pb.firstName );         return fNameCmp;     } } 

Comments

Whether it's a set of integers, a list of names, or records in a database, sometimes you need to sort a group of values. Sorting makes it easier to both manually and programmatically search for an individual item within a large group of values. The Array and ArrayList collection classes allow you to sort a group of values for this purpose. One thing to note is that these are the only collection classes that allow sorting. Fortunately, you can easily sort a group of values from a different collection class by converting its keys and values into an array. Furthermore, if you want to keep a sorted list of values at all times, even when new items are added, you can use the SortedList class.

At the simplest level, the Array and ArrayList can perform a default sort on the values by simply either passing the array to sort to the Sort method if using the Array class or calling the Sort instance method in the ArrayList class, which doesn't need any parameters. This method works well for data types that are defined within the .NET Framework, but when you need to sort a custom data type, you need to help the Sort method by creating a custom comparison method.

In the code listing earlier, you can see a struct that represents a person. A Person simply contains fields denoting first and last names, which are string objects. If you pass an array of Person values into a Sort method without any type of custom comparison method, you get unexpected results or at least results that are undesirable. Therefore, you create a custom comparison method named Compare , which is declared in the IComparer interface. The method defined in the Person struct compares two Person objects based on their last names. If the last names are equal, then it makes a comparison on the first names. When sorting an array of these objects, repeatedly calling the Compare method, which the Sort method can do, will result in a list of names sorted by last names in ascending order and first names in ascending order for those objects with equal last names.

To use the Compare method defined here, you have to pass a created object of this type into the Sort method. The Sort can accept an IComparer object as the last parameter, and because the Person struct implements that interface, an implicit cast occurs. Listing 4.5 shows how to use the Person struct defined earlier by first allowing the user to input a list of first and last names. When the user is finished, the unsorted array is printed to the console. You then call the Sort method of the ArrayList class, passing an instance of a Person to use the Compare method of that object.

Listing 4.5 Sorting Names by Last Name and First Name Using the Compare Method in the Person Object

 using System; using System.Collections; namespace _11_Sorting {     class Class1     {         [STAThread]         static void Main(string[] args)         {             string input;             ArrayList alPeople = new ArrayList();             Console.Write( "Enter first and last name or 'q' to quit: " );             input = Console.ReadLine();             // get list of names from user             while( input.Length != 1  Char.ToUpper(input[0]) != 'Q' )             {                 string[] name = input.Split( new char[]{' '}, 2 );                 alPeople.Add( new Person( name[0], name[1] ));                 Console.Write( "Enter first and last name or 'q' to quit: " );                 input = Console.ReadLine();             }             // output unsorted names             Console.WriteLine( "\nArray before sort" );             foreach( Person p in alPeople )             {                 Console.WriteLine( "   {0} {1}", p.firstName, p.lastName );             }             // sort arraylist using custom IComparer             alPeople.Sort( new Person() );             // output sorted array             Console.WriteLine( "\nArray after sort" );             foreach( Person p in alPeople )             {                 Console.WriteLine( "   {0} {1}", p.firstName, p.lastName );             }         }     }     // person definition here... }