Sorting and searching: Arrays

Sorting and searching

Java 1.2 adds utilities to perform sorting and searching for arrays or Lists. These utilities are static methods of two new classes: Arrays for sorting and searching arrays, and Collections for sorting and searching Lists.

Arrays

The Arrays class has an overloaded sort( ) and binarySearch( ) for arrays of all the primitive types, as well as for String and Object. Here's an example that shows sorting and searching an array of byte (all the other primitives look the same) and an array of String:

The first part of the class contains utilities to generate random String objects using an array of characters from which random letters can be selected. randString( ) returns a string of any length, and randStrings( ) creates an array of random Strings, given the length of each String and the desired size of the array. The two print( ) methods simplify the display of the sample arrays. In main( ), Random.nextBytes( ) fills the array argument with randomly-selected bytes. (There are no corresponding Random methods to create arrays of the other primitive data types.) Once you have an array, you can see that it's only a single method call to perform a sort( ) or binarySearch( ). There's an important warning concerning binarySearch( ): If you do not call sort( ) before you perform a binarySearch( ), unpredictable behavior can occur, including infinite loops.

Sorting and searching with Strings looks the same, but when you run the program you'll notice something interesting: the sorting is lexicographic, so uppercase letters precede lowercase letters in the character set. Thus, all the capital letters are at the beginning of the list, followed by the lowercase letters, so 'Z' precedes 'a'. It turns out that even telephone books are typically sorted this way.

Comparable and Comparator

What if this isn't what you want? For example, the index in this book would not be too useful if you had to look in two places for everything that begins with 'A' or 'a'.

When you want to sort an array of Object, there's a problem. What determines the ordering of two Objects? Unfortunately, the original Java designers didn't consider this an important problem, or it would have been defined in the root class Object. As a result, ordering must be imposed on Objects from the outside, and the new collections library provides a standard way to do this (which is almost as good as defining it in Object).

There is a sort( ) for arrays of Object (and String, of course, is an Object) that takes a second argument: an object that implements the Comparator interface (part of the new collections library) and performs comparisons with its single compare( ) method. This method takes the two objects to be compared as its arguments and returns a negative integer if the first argument is less than the second, zero if they're equal, and a positive integer if the first argument is greater than the second. With this knowledge, the String portion of the example above can be re-implemented to perform an alphabetic sort:

By casting to String, the compare( ) method implicitly tests to ensure that it is used only with String objects - the run-time system will catch any discrepancies. After forcing both Strings to lower case, the String.compareTo( ) method produces the desired results.

When you use your own Comparator to perform a sort( ), you must use that same Comparator when using binarySearch( ).

The Arrays class has another sort( ) method that takes a single argument: an array of Object, but with no Comparator. This sort( ) method must also have some way to compare two Objects. It uses the natural comparison method that is imparted to a class by implementing the Comparable interface. This interface has a single method, compareTo( ), which compares the object to its argument and returns negative, zero, or positive depending on whether it is less than, equal to, or greater than the argument. A simple example demonstrates this:

Of course, your compareTo( ) method can be as complex as necessary.

Lists

A List can be sorted and searched in the same fashion as an array. The static methods to sort and search a List are contained in the class Collections, but they have similar signatures as the ones in Arrays: sort(List) to sort a List of objects that implement Comparable, binarySearch(List, Object) to find an object in the list, sort(List, Comparator) to sort a List using a Comparator, and binarySearch(List, Object, Comparator) to find an object in that list. This example uses the previously-defined CompClass and AlphaComp to demonstrate the sorting tools in Collections:

The use of these methods is identical to the ones in Arrays, but you're using a List instead of an array.

The TreeMap must also order its objects according to Comparable or Comparator.