#138 – Searching a Sorted Array

If an array is already sorted and if the type that its elements belong to has implemented IComparable, you can use the BinarySearch method to quickly search for a particular element.

Using our earlier example, with a Person class that implements IComparable (sorts by LastName/FirstName), we can search for a particular Person in a sorted array:

            Person[] folks = new Person[4];
            folks[0] = new Person("Bronte", "Emily");
            folks[1] = new Person("Bronte", "Charlotte");
            folks[2] = new Person("Tennyson", "Alfred");
            folks[3] = new Person("Mailer", "Norman");

            // Sort
            Array.Sort(folks);    // C. Bronte, E. Bronte, Mailer, Tennyson

            // Now search - returns index of 2 (3rd element)
            int normIndex = Array.BinarySearch(folks, new Person("Mailer", "Norman"));
            Person norm = folks[normIndex];     // Get reference to Normal

If you have a property not used for sorting purposes (e.g. Person.Age), you can’t be guaranteed that the object returned as a match actually matches your specified object–for that property.  Only properties used for comparison are guaranteed to match in the object returned.

Advertisements

#137 – Sorting an Array Using an Independent Comparer Method

Instead of extending a type to implement IComparable to allow sorting, you can create a separate class that knows how to compare objects of that type and use the new class to do the sorting.

Here’s an example of sorting objects of type Person using a custom Compare method.  To start with, we define a new class that implements IComparer.

        public class PersonSorter : IComparer
        {
            public int Compare(object o1, object o2)
            {
                Person p1 = o1 as Person;
                Person p2 = o2 as Person;

                // Sort by LastName, then by FirstName (ignore case)
                int compare = p1.LastName.ToLower().CompareTo(p2.LastName.ToLower());
                if (compare == 0)
                    compare = p1.FirstName.ToLower().CompareTo(p2.FirstName.ToLower());

                return compare;
            }
        }

Now we can sort using this compare function by passing an instance of the IComparer class into the Sort method.

            Person[] folks = new Person[4];
            folks[0] = new Person("Bronte", "Emily");
            folks[1] = new Person("Bronte", "Charlotte");
            folks[2] = new Person("Tennyson", "Alfred");
            folks[3] = new Person("Mailer", "Norman");

            Array.Sort(folks, new PersonSorter());

#136 – Sorting an Array of Values Based on an Array of Keys

You can use the Array.Sort method to sort two arrays at the same time.  The values of one array are used as the keys to determine the sort order and the values of the second array are just changed to match the sequence of the first array.

Array.Sort takes two arrays.  The first is an array of keys, dictating how the elements will be sorted.  The second will just be reordered to match the sequence of the first array.

Here’s an example:

            string[] titles = { "Pride and Prejudice", "Moby-Dick", "A Tale of Two Cities",
                                "Anna Karenina", "Fahrenheit 451" };
            string[] firstWords = {
                "It is a truth universally acknowledged",
                "Call me Ishmael",
                "It was the best of times",
                "All happy families are alike",
                "It was a pleasure to burn" };

            Array.Sort(titles, firstWords);   // Sort by title

Here’s what both arrays look like after sorting:

#135 – Implementing IComparable to Allow Sorting a Custom Type

Arrays of elements that belong to a custom type cannot be sorted, unless the type implements the IComparable interface.

To make elements of a custom type sortable, you need to implement IComparable in your type.  IComparable consists of the single method CompareTo, which compares two objects.

Here’s an example of a Person class implementing CompareTo to sort people in LastName/FirstName order:

            public int CompareTo(object obj)
            {
                Person other = obj as Person;
                if (other == null)
                    throw new ArgumentException("Object is not a Person");
                else
                {
                    // Sort by LastName, then by FirstName (ignore case)
                    int compare = this.LastName.ToLower().CompareTo(other.LastName.ToLower());
                    if (compare == 0)
                        compare = this.FirstName.ToLower().CompareTo(other.FirstName.ToLower());

                    return compare;
                }

Here’s an example of sorting an array of Person objects:

            Person[] folks = new Person[4];
            folks[0] = new Person("Bronte", "Emily");
            folks[1] = new Person("Bronte", "Charlotte");
            folks[2] = new Person("Tennyson", "Alfred");
            folks[3] = new Person("Mailer", "Norman");
            Array.Sort(folks);    // C. Bronte, E. Bronte, Mailer, Tennyson

#134 – Sorting One-Dimensional Arrays

You can sort a one-dimensional array of elements using the static Array.Sort method.  This requires that the underlying type of the array elements implements the IComparable interface.  Types that implement IComparable include: all built-in numeric types (e.g. int, float, double), char, string and DateTime types.

Here’s an example that sorts an array of integers:

 int[] nums = new int[5];
 nums[0] = 3; nums[1] = 2; nums[2] = 4;
 nums[3] = 1; nums[4] = 0;

 Array.Sort(nums);   // Elements now: 0, 1, 2, 3, 4

Here’s an example of sorting an array of strings:

 string[] emps = new string[4];
 emps[0] = "Augustus";
 emps[1] = "Tiberius";
 emps[2] = "Caligula";
 emps[3] = "Claudius";
 Array.Sort(emps);   // Augustus, Caligula, Claudius, Tiberius

You can’t sort an array of objects, if the element type does not implement IComparable:

 Cat[] cats = new Cat[2];
 cats[0] = new Cat("Garfield", "Sleep all day");
 cats[1] = new Cat("Buster", "Scratch everything");
 Array.Sort(cats);    // throws InvalidOperationException