Learn how to sort an array efficiently using the sort() method and a custom Comparator in Java.
Sorting is a common task in programming, and sorting arrays of strings is no exception. For example, you might want to sort a list of the items sold by an online store or a list of customer names and e-mail addresses. Fortunately, Java makes sorting arrays of string easy because it provides the sort( ) utility method, which is defined by the Arrays class in java.util. In its default form, sort( ) orders strings in case-sensitive, alphabetical order, and this is fine for many situations. However, sometimes you want to sort an array of strings in reverse alphabetical order. This requires a bit more work. There are a number of ways to approach the problem of sorting in reverse. For example, one naive solution is to sort the array and then copy it back to front into another array. Besides lacking elegance, this technique is also inefficient. Fortunately, Java provides a simple, yet effective way to reverse-sort an array of strings. This approach uses a custom Comparator to specify how the sort should be conducted and a version of sort( ) that takes the Comparator as an argument.
Step-by-Step
Sorting an array of strings in reverse involves these three steps:
1. Create a Comparator that reverses the outcome of a comparison between two strings.
2. Create an object of that Comparator.
3. Pass both the array to be sorted and the Comparator to a version of java.util.Arrays.sort( ) that takes a comparator as an argument. When sort( ) returns, the array will be sorted in reverse.
Discussion
Comparator is a generic interface that is declared as shown here:
Comparator<T>
The type parameter T specifies the type of data that will be compared. In this case, String will be passed to T.
Comparator defines the following two methods:
int compare(T objA, T objB)
boolean equals(Object obj)Of these, only compare( ) must be implemented. The equals( ) method simply specifies an override of equals( ) in Object. Implementing equals( ) enables you to determine if two Comparators are qual. However, this capability is not always needed. When it is not needed (as it is not in the examples in this chapter), there is no need to override Object’s implementation.
The method in which we are interested is compare( ). It determines how one object compares to another. Normally, it must return less than zero if objA is less than objB, greater than zero if objA is greater than objB, and zero if the two objects are equal. Implementing compare( ) in this way causes it to operate according to the natural ordering of the data. For strings, this means alphabetical order. However, you are free to implement compare( ) to suit the needs of your task. To reverse-sort an array of strings, you will need to create a version of compare( ) that reverses the outcome of the comparison.
Here is one way to implement a reverse comparator for Strings.
// Create a Comparator that returns the outcome
// of a reverse string comparison.
class RevStrComp implements Comparator<String>
{
// Implement the compare() method so that it
// reverses the order of the string comparison.
public int compare(String strA, String strB)
{
// Compare strB to strA, rather than strA to strB.
return strB.compareTo(strA);
}
}Let’s look at RevStrComp closely. First, notice that RevStrComp implements Comparator. This means that an object of type RevStrComp can be used any place that a Comparator is needed. Also notice that it implements a String-specific version of Comparator. Thus, RevStrComp is not, itself, generic. It works only with strings. Now, notice that the compare( ) method calls String’s compareTo( ) method to compare two strings. compareTo( ) is specified by the Comparable interface, which is implemented by String (and many other classes). A class that implements Comparable guarantees that objects of the class can be ordered. The general form of compareTo( ) as implemented by String is shown here:
int compareTo(String str)It returns less than zero if the invoking string is less than str, greater than zero if the invoking string is greater than str, and zero if they are equal. One string is less than another if it comes before the other in alphabetical order. One string is greater than another if it comes after the other in alphabetical order.
The compare( ) method of RevStrComp returns the result of the call to compareTo( ). However, notice that compare( ) calls compareTo( ) in reverse order. That is, compareTo( ) is called on strB with strA passed as an argument. For a normal comparison, strA would invoke compareTo( ), passing strB. However, because strB invokes compareTo( ), the outcome of the comparison is reversed. Therefore, the ordering of the two strings is reversed. Once you have created a reverse comparator, create an object of that comparator and pass it to this version of sort( ) defined by java.util.Arrays:
static <T> void sort(T[ ] array, Comparator<? super T> comp)Notice the super clause. It ensures that the array passed to sort( ) is compatible with the type of Comparator. After the call to sort( ), the array will be in reverse alphabetical order.
Example
The following example reverse-sorts an array of strings. For demonstration purposes, it also sorts them in natural, alphabetical order using the default version of sort( ).
// Sort an array of strings in reverse order.
import java.util.*;
// Create a Comparator that returns the outcome
// of a reverse string comparison.
class RevStrComp implements Comparator<String>
{
// Implement the compare() method so that it
// reverses the order of the string comparison.
public int compare(String strA, String strB)
{
// Compare strB to strA, rather than strA to strB.
return strB.compareTo(strA);
}
}
// Demonstrate the reverse string comparator.
class RevStrSort
{
public static void main(String args[])
{
// Create a sample array of strings.
String strs[] = { "dog", "horse", "zebra", "cow", "cat" };
// Show the initial order.
System.out.print("Initial order: ");
for(String s : strs)
System.out.print(s + " ");
System.out.println("\n");
// Sort the array in reverse order.
// Begin by creating a reverse string comparator.
RevStrComp rsc = new RevStrComp();
// Now, sort the strings using the reverse comparator.
Arrays.sort(strs, rsc);
// Show the reverse sorted order.
System.out.print("Sorted in reverse order: ");
for(String s : strs)
System.out.print(s + " ");
System.out.println("\n");
// For comparison, sort the strings in natural order.
Arrays.sort(strs);
// Show the natural sorted order.
System.out.print("Sorted in natural order: ");
for(String s : strs)
System.out.print(s + " ");
System.out.println("\n");
}
}The output from this program is shown here:
Initial order: dog horse zebra cow cat
Sorted in reverse order: zebra horse dog cow cat
Sorted in natural order: cat cow dog horse zebraOptions and Alternatives
Although this recipe sorts strings in reverse alphabetical order, the same basic technique can be generalized to other situations. For example, you can reverse-sort other types of data by
creating the appropriate Comparator. Simply adapt the approach shown in the example.
The compareTo( ) method defined by String is case-sensitive. This means that uppercase and lowercase letters will be sorted separately. You can sort data independent of case differences by using compareToIgnoreCase( ). (See Ignore Case Differences When Sorting an Array of Strings).
You can sort strings based on some specific substring. For example, if each string contains a name and an e-mail address, then you could create a comparator that sorts on the e-mail address portion of each string. One way to approach this is to use the regionMatches( ) method. You can also sort by some criteria other than a strict alphabetic relationship. For example, strings representing pending tasks could be sorted in order of priority.
