Custom Sorting – Sort Method

The Sort method allows you to sort collections, as long as the items are of the same base data type. If the items are objects, however, the collection doesn’t know how to sort them. If you want to sort objects, you must help the collection a little by telling it how to compare the objects. A sorting operation is nothing more than a series of comparisons. Sorting algorithms compare items and swap them if necessary.

All the information needed by a sorting algorithm to operate on an item of any type is a function that compares two objects. Let’s say you have a list of persons, and each person is a structure that contains names, addresses, e-addresses, and so on. The System.Collections class can’t make any assumptions as to how you want your list sorted. This collection can be sorted by any field in the structure (names, e-addresses, postal codes, and so on).

The comparer is implemented as a separate class, outside all other classes in the project, and is specific to a custom data type. Let’s say you have created a custom structure for storing contact information. The Person object is declared as a structure with the following fields:

Structure Person
	Dim Name As String
	Dim BDate As Date
	Dim EMail As String
End StructureCode language: JavaScript (javascript)

You’ll probably build a class to represent persons, but I’m using a Structure to simplify the code. To add an instance of the Person object to an ArrayList or HashTable, create a variable of Person type, initialize its fields, and then add it to the aList ArrayList via the Add method. This collection can’t be sorted with the simple forms of the Sort method because the compiler doesn’t know how to compare two Person objects. You must provide your own function for comparing two variables of the Person type. After this function is written, the compiler can compare items and therefore sort the collection. This custom function, however, can’t be passed to the Sort and BinarySearch methods by name. You must create a new class that implements the IComparer interface and pass an IComparer object to the two methods.

Implementing the IComparer Interface

Here’s the outline of a class that implements the IComparer interface:

Class customComparer : Implements IComparer
	Public Function Compare( _
			ByVal o1 As Object, ByVal o2 As Object) _
			As Integer Implements IComparer.Compare
		{ function’s code }
	End Function
End ClassCode language: JavaScript (javascript)

The name of the class can be anything. It should be a name that indicates the type of comparison it performs or the type of objects it compares. After the class declaration, you must specify the interface implemented by the class. As soon as you type the first line of the preceding code segment, the editor will insert automatically the stub of the Compare function. The name of the customfunction must be Compare and it must implement the IComparer.Compare interface. The interface declares a placeholder for a function, whose code must be provided by the developer.

Let’s get back to our example. To use the custom function, you must create an object of the customComparer type (or whatever you have named the class) and then pass it to the Sort and BinarySearch methods as an argument:

Dim CompareThem As New customComparer
aList.Sort(CompareThem)Code language: PHP (php)

You can combine the two statements in one by initializing the customComparer variable in the line that calls the Sort method:

aList.Sort(New customComparer)Code language: CSS (css)

You can also use the equivalent syntax of the BinarySearch method to locate a custom object that implements its own IComparer interface:

aList.BinarySearch(object, New customComparer)Code language: CSS (css)

This is how you can use a custom function to compare two objects. Everything is the same, except for the name of the comparer, which is different every time.

The last step is to implement the function that compares the two objects and returns an integer value, indicating the order of the elements. This value should be −1 if the first object is smaller than the second object, 0 if the two objects are equal, and 1 if the first object is larger than the second object. Smaller here means that the element appears before the larger one when sorted in ascending order. Listing 10.13 is the function that sorts Person objects according to the BDate field. The sample code for this and the following section comes from the CustomComparer project.

Themain form contains a single button, which populates the collection and then prints the original collection, the collection sorted by name, and the collection sorted by birth date.

Listing 10.13: A Custom Comparer

Class PersonAgeComparer : Implements IComparer
	Public Function Compare(ByVal o1 As Object, _
			ByVal o2 As Object) As Integer _
			Implements IComparer.Compare
		Dim person1, person2 As Person
		Try
			person1 = CType(o1, Person)
			person2 = CType(o2, Person)
		Catch compareException As System.Exception
			Throw (compareException)
			Exit Function
		End Try
		If person1.BDate > person2.BDate Then
			Return -1
		Else
			If person1.BDate < person2.BDate Then
				Return 1
			Else
			Return 0
				End If
		End If
	End Function
End ClassCode language: JavaScript (javascript)

The code could have been considerably simpler, but I’ll explain momentarily why the Try statement is necessary. The comparison takes place in the If statement. If the first person’s birth date is chronologically earlier than the second person’s, the function returns the value −1. If the first person’s birth date is chronologically later than the second person’s, the function returns 1. Finally, if the two values are equal, the function returns 0.

The code is straightforward, so why the error-trapping code? Before we perform any of the necessary operations, we convert the two objects into Person objects. It’s not unthinkable that the collection with the objects you want to sort contains objects of different types. If that’s the case, the CType() function won’t be able to convert the corresponding argument to the Person type, and the comparison will fail. The same exception that would be thrown in the function’s code is raised again from within the error handler, and it’s passed back to the calling code.

Implementing Multiple Comparers

The Person objects can be sorted in many ways. You might wish to sort them by ID, name, and so on. To accommodate multiple sorts, you must implement several classes, each one with a different Compare function. Listing 10.14 shows two classes that implement two different Compare functions for the Person class. The PersonNameComparer class compares the names, whereas the PersonAgeComparer class compares the ages. Both classes, however, implement the IComparer interface.

Listing 10.14: A Class with Two Custom Comparers

Class PersonNameComparer : Implements IComparer
	Public Function Compare(ByVal o1 As Object, _
			ByVal o2 As Object) As Integer _
			Implements IComparer.Compare
		Dim person1, person2 As Person
		Try
			person1 = CType(o1, Person)
			person2 = CType(o2, Person)
		Catch compareException As System.Exception
			Throw (compareException)
			Exit Function
		End Try
		If person1.Name < person2.Name Then
			Return -1
		Else
			If person1.Name > person2.Name Then
				Return 1
			Else
				Return 0
			End If
		End If
	End Function
End Class

Class PersonAgeComparer : Implements IComparer
	Public Function Compare(ByVal o1 As Object, _
			ByVal o2 As Object) As Integer _
			Implements IComparer.Compare
		Dim person1, person2 As Person
		Try
			person1 = CType(o1, Person)
			person2 = CType(o2, Person)
		Catch compareException As System.Exception
			Throw (compareException)
			Exit Function
		End Try
		If person1.BDate > person2.BDate Then
			Return -1
		Else
			If person1.BDate < person2.BDate Then
				Return 1
			Else
			Return 0
				End If
		End If
	End Function
End ClassCode language: JavaScript (javascript)

To test the custom comparers, create a new application and enter the code of Listing 10.14 (the two classes) in a separate Class module. Don’t forget to include the declaration of the Person structure. Then place a button on the form and enter the code of Listing 10.15 in its Click event handler. This code adds three persons with different names and birth dates to an ArrayList.

Listing 10.15: Testing the Custom Comparers

Private Sub TestComparers(ByVal sender As System.Object, _
		ByVal e As System.EventArgs) Handles bttnComparerTest.Click
	Dim AList As New ArrayList
	Dim p As Person
	' POPULATE COLLECTION
	p.Name = "C Person"
	p.EMail = "[email protected]"
	p.BDate = #1/1/1961#
	' ADD FIRST PERSON
	If Not AList.Contains(p) Then AList.Add(p)
	p.Name = "A Person"
	p.EMail = "[email protected]"
	p.BDate = #3/3/1961#
	' ADD SECOND PERSON
	If Not AList.Contains(p) Then AList.Add(p)
	p.Name = "B Person"
	p.EMail = "[email protected]"
	p.BDate = #12/2/1961#
	' ADD THIRD PERSON
	If Not AList.Contains(p) Then AList.Add(p)
	' PRINT COLLECTION AS IS
	p.Name = "D Person"
	p.EMail = "[email protected]"
	p.BDate = #6/2/1961#
	' ADD FOURTH PERSON
	If Not AList.Contains(p) Then AList.Add(p)
	' Now sort the collection in all possible ways
	Dim PEnum As IEnumerator
	PEnum = AList.GetEnumerator
	ListBox1.Items.Add("Original Collection")
	While PEnum.MoveNext
		ListBox1.Items.Add(CType(PEnum.Current, Person).Name & _
				vbTab & CType(PEnum.Current, Person).BDate)
	End While
	' SORT BY NAME, THEN PRINT COLLECTION
	ListBox1.Items.Add(" ")
	ListBox1.Items.Add("Collection Sorted by Name")
	' USE THE PersonNameComparer TO SORT ARRAYLIST BY NAME FIELD
	AList.Sort(New PersonNameComparer)
	PEnum = AList.GetEnumerator
	While PEnum.MoveNext
		ListBox1.Items.Add(CType(PEnum.Current, Person).Name & _
				vbTab & CType(PEnum.Current, Person).BDate)
	End While
	' SORT BY AGE, THEN PRINT COLLECTION
	ListBox1.Items.Add(" ")
	ListBox1.Items.Add("Collection Sorted by Age")
	' USE THE PersonAgeComparer TO SORT ARRAYLIST BY BDATE FIELD
	AList.Sort(New PersonAgeComparer)
	PEnum = AList.GetEnumerator
	While PEnum.MoveNext
		ListBox1.Items.Add(CType(PEnum.Current, Person).Name & _
				vbTab & CType(PEnum.Current, Person).BDate)
	End While
End SubCode language: PHP (php)

The four sections of the code are delimited by comments in the listing. The first section populates the collection with three variables of the Person type. The second section prints the items in the order in which they were added to the collection:

C Person 1/1/1961
A Person 3/3/1961
B Person 2/2/1961

The third section of the code calls the Sort method, passing the PersonNameComparer custom comparer as an argument, and it again prints the contents of the ArrayList. The names are listed now in alphabetical order:

A Person 3/3/1961
B Person 2/2/1961
C Person 1/1/1961

In the last section, it calls the Sort method again — this time to sort the items by age — and prints them:

C Person 1/1/1961
B Person 2/2/1961
A Person 3/3/1961

It is straightforward to write your own custom comparers and sort your custom object in any way that suits your application. Custom comparisons might include more-complicated calculations, not just comparisons. For example, you can sort Rectangles by their area, color values by their hue or saturation, and customers by the frequency of their orders.

Custom Sorting of a SortedList

The items of a SortedList are sorted according to their keys. Of course, the SortedList cannot maintain the order of the keys unless the keys are of a base type, such as integers or strings. If you need to use objects as keys, you must simply provide a function to implement the IComparer interface, as you know well by now, and pass the name of the class that implements the interface to the constructor of the SortedList class.