Sorting Arrays

Arrays are indexed sets of data, and this is how we’ve used them so far in this website. In this section, you will learn about additional members that make arrays extremely flexible. The System.Array class provides methods for sorting arrays, searching for an element, and more. In the past, programmers spent endless hours writing code to perform the same operations on arrays, but the Framework frees them from similar counterproductive tasks.

This chapter starts with a discussion of the advanced features of the Array class. After you know how to make the most of arrays, We’ll discuss the limitations of arrays and then move on to other collections that overcome these limitations.

To sort an array, call its Sort method. This method is heavily overloaded and, as you will see, it is possible to sort an array based on the values of another array, or even supply your own custom sorting routines. If the array is sorted, you can call the BinarySearch method to locate an element very efficiently. If not, you can still locate an element in the array by using the IndexOf and LastIndexOf methods. The Sort method is a reference method: It requires that you supply the name of the array to be sorted as an argument. The simplest form of the Sort method accepts a single argument, which is the name of the array to be sorted:

Array.Sort(arrayName)Code language: JavaScript (javascript)

This method sorts the elements of the array according to the type of its elements, as long as the array is strictly typed and was declared as a simple data type (String, Decimal, Date, and so on). If the array contains data that are not of the same type, or they’re objects, the Sort method will fail. The Array class just doesn’t know how to compare integers to strings or dates, so don’t attempt to sort arrays whose elements are not of the same type. If you can’t be sure that all elements are of the same type, use a Try. . .Catch statement.

You can also sort a section of the array by using the following form of the Sort method, where startIndex and endIndex are the indices that delimit the section of the array to be sorted:

System.Array.Sort(arrayName, startIndex, endIndex)Code language: CSS (css)

An interesting variation of the Sort method sorts the elements of an array according to the values of the elements in another array. Let’s say you have one array of names and another of matching Social Security numbers. It is possible to sort the array of names according to their Social Security numbers. This form of the Sort method has the following syntax:

System.Array.Sort(array1, array2)Code language: CSS (css)

array1 is the array with the keys (the Social Security numbers), and array2 is the array with the actual elements to be sorted. This is a very handy form of the Sort method. Let’s say you have a list of words stored in one array and their frequencies in another. Using the first form of the Sort method, you can sort the words alphabetically. With the third form of the Sort method, you can sort them according to their frequencies (starting with the most common words and ending with the least common ones). The two arrays must be one-dimensional and have the same number of elements. If you want to sort a section of the array, just supply the startIndex and endIndex arguments to the Sort method, after the names of the two arrays.

The SortArrayByLength application (download the source code), shown in Figure 10.1, demonstrates how to sort an array based on the length of its elements (short elements appear at the top of the array, whereas longer elements appear near the bottom of the array). First, it populates the array MyStrings with a few strings and then it assigns the lengths of these strings to the matching elements of the array MyStringsLen. The MyStrings(0) element’s value is Visual Basic, and the MyStringsLen(0) element’s value is 12. After the two arrays have been populated, the code sorts the elements of the MyStrings array according to the values of the MyStringsLen array. The statement that sorts the array is the following:

System.Array.Sort(MyStringsLen, MyStrings)Code language: CSS (css)

The code, which also displays the arrays before and after sorting, is shown in Listing 10.1.

Listing 10.1: Sorting an Array According to the Length of Its Elements

Protected Sub Button1 Click(...) Handles Button1.Click
	Dim MyStrings(3) As String
	’ populate MyStrings array
	Dim MyStringsLen(3) As Integer
	MyStrings(0) = "Visual Basic"
	MyStrings(1) = "C++"
	MyStrings(2) = "C#"
	MyStrings(3) = "HTML"
	’ populate MyStringsLen array
	Dim i As Integer
	For i = 0 To UBound(MyStrings)
		MyStringsLen(i) = len(MyStrings(i))
	Next
	ListBox1.Items.Clear()
	ListBox1.Items.Add("Original Array")
	ListBox1.Items.Add("*************************")
	Dim str As Integer
	For str = 0 To UBound(MyStrings)
		ListBox1.Items.Add(MyStrings(str) & " " & MyStringsLen(str).ToString)
	Next
	ListBox1.Items.Add("*************************")
	ListBox1.Items.Add("Array Sorted According to String Length ")
	ListBox1.Items.Add("*************************")
	' sort MyStrings array based on MyStringsLen array
	System.Array.Sort(MyStringsLen, MyStrings)
	For str = 0 To UBound(MyStrings)
		ListBox1.Items.Add(MyStrings(str) & " " & _
				MyStringsLen(str).ToString)
	Next
End SubCode language: PHP (php)

The output produced by the SortArrayByLength application in the ListBox control is shown here:

Original Array
*************************
Visual Basic 12
C++ 3
C# 2
HTML 4
*************************
Array Sorted According to String Length
*************************
C# 2
C++ 3
HTML 4
Visual Basic 12Code language: PHP (php)

Notice that the Sort method sorts both the auxiliary array (the one with the lengths of the strings) and the main array, so that the two arrays are always in synch. After the call to the Sort method, the first element in the MyStrings array is C#, and the first element in the MyStringsLen array is 2.

The array with the keys that determine the order of the elements can be anything. If the array to be sorted holds some rectangles, you can create an auxiliary array that contains the area of the rectangles and sort the original array according to the area of its rectangles. Likewise, an array of colors can be sorted according to the hue or the luminance of each color component, and so on.

Another form of the Sort method uses a user-supplied function to sort arrays of customobjects. As you recall, arrays can store all types of objects. But the Framework doesn’t know how to sort your custom objects. To sort an array of objects, you must provide your own class that implements the IComparer interface (basically, a function that can compare two instances of a custom class). This form of the Sort method is described in detail in the section titled ‘‘Custom Sorting,’’ later in this chapter. By the way, you can create a function to sort an array based on the length of its elements or any other property of its elements, similar to the Sort method that uses the items of an auxiliary array as keys.