Sorting an array
With the built-in sorting methods, you can sort any array of primitives, or any array of objects that either implements Comparable or has an associated Comparator. This fills a big hole in the Java libraries; believe it or not, there was no support in Java 1.0 or 1.1 for sorting Strings! Here’s an example that generates random String objects and sorts them:
//: c11:StringSorting.java
// Sorting an array of Strings.
import com.bruceeckel.util.*;
import java.util.*;
public class StringSorting {
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa, new Arrays2.RandStringGenerator(5));
System.out.println(
"Before sorting: " + Arrays.asList(sa));
Arrays.sort(sa);
System.out.println(
"After sorting: " + Arrays.asList(sa));
}
} ///:~
One thing you’ll notice about the output in the String sorting algorithm is that it’s lexicographic, so it puts all the words starting with uppercase letters first, followed by all the words starting with lowercase letters. (Telephone books are typically sorted this way.) You may also want to group the words together regardless of case, and you can do this by defining a Comparator class, thereby overriding the default String Comparable behavior. For reuse, this will be added to the “util” package:
//: com:bruceeckel:util:AlphabeticComparator.java
// Keeping upper and lowercase letters together.
package com.bruceeckel.util;
import java.util.*;
public class AlphabeticComparator implements Comparator {
public int compare(Object o1, Object o2) {
String s1 = (String)o1;
String s2 = (String)o2;
return s1.toLowerCase().compareTo(s2.toLowerCase());
}
} ///:~
By casting to String at the beginning, you’ll get an exception if you attempt to use this with the wrong type. Each String is converted to lowercase before the comparison. String’s built-in compareTo( ) method provides the desired functionality.
Here’s a test using AlphabeticComparator:
//: c11:AlphabeticSorting.java
// Keeping upper and lowercase letters together.
import com.bruceeckel.util.*;
import java.util.*;
public class AlphabeticSorting {
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa, new Arrays2.RandStringGenerator(5));
System.out.println(
"Before sorting: " + Arrays.asList(sa));
Arrays.sort(sa, new AlphabeticComparator());
System.out.println(
"After sorting: " + Arrays.asList(sa));
}
} ///:~
The sorting algorithm that’s used in the Java standard library is designed to be optimal for the particular type you’re sorting—a Quicksort for primitives, and a stable merge sort for objects. So you shouldn’t need to spend any time worrying about performance unless your profiler points you to the sorting process as a bottleneck.
