Sort it
out
Tutorial Details:
Sort it out
Sort it out
By: By Alex Blewitt
Use the Comparable and Comparator interfaces to sort data in Java
ave you ever wondered how to sort elements in a List ? Java's collections classes and interfaces (in the java.util package) provide the ability to sort arbitrary datasets. In this article, we look at how to sort elements stored in List s, how to provide sorting orders for data classes, and how to use a generic mechanism for sorting JavaBeans.
This article specifically covers:
How sorting algorithms work
How the Comparable interface provides a natural sorting order and how to sort a list of String s into lexicographical order
How additional sorting orders can be used with existing classes by using the Comparator interface and how a generic JavaBeans sorting mechanism sorts arbitrary JavaBeans with BeanPropertyComparator
How multiple sorts apply to a single collection, as demonstrated by CompositeComparator
Download the source code associated with this article from Resources .
How sorting works
We start with how sorting algorithms work. Although you don't need to implement sorting algorithms yourself, it's useful to know how they work internally. You can skip to the next section if you just want to jump straight to the code.
It is much easier to find an item from a sorted dataset rather than an unsorted dataset. For example, if you want to look up liberty 's definition in a dictionary, you begin by locating the L section and then scan for words starting with li until you finally find liberty . This process would take much longer if the dictionary was a randomly ordered jumble of words.
When you look up a word in the dictionary, you compare a random word with the target word. If the target word you're searching for is "greater" than the random word you've just found, then you know the target word follows the other word; conversely, if the target word is "smaller" than the one you've just found, then you know that the target word precedes it. You then move in the right direction, and the process repeats until you find the target word.
Finding data in Java is easy using a sorted data structure. There are two data structures in the standard Java collections package that sort automatically: the interfaces SortedSet and SortedMap , which are implemented by TreeSet and TreeMap , respectively.
How do these collections know how to sort arbitrary classes? The sorting algorithms use a process similar to the dictionary example?repeated pair-wise data comparisons.
Several well-known sorting algorithms exist; the exact implementations and differences between them are outside this article's scope. However, one Java demo, which you may have downloaded with your Java SDK, called the Sorting Algorithm Demo , graphically shows the speed differences between various sorting algorithms. (Click on each applet to see the sorting algorithms work.)
The simplest sorting algorithm?the bubble sort?picks a dataset's first element. It then runs through the remainder of the list until it finds one "smaller" than the one it already has. It locates the list's smallest element and puts it at the top of the list. The process then repeats, starting at the second element, to find the next smallest, and so on until the process reaches the end.
Although more efficient sorting algorithms, such as the appropriately named quick sort, exist, the common behavior in all sorting algorithms is repeated comparison between different elements. Elements are compared to determine which is smaller or greater at each step of the process.
Sort collections
The Collections class in Java provides a sort() method that allows a (modifiable) list to be sorted. The following code sample shows how a List can be created from an array, and then sorted using the Collections.sort() method:
// Needs to import java.util.*;
Object[] data = {"Kiwi","Banana","Mango","Aubergine","Strawberry"};
List list = Arrays.asList(data);
Collections.sort(list);
System.out.println(list);
// Displays [Aubergine, Banana, Kiwi, Mango, Strawberry]
The first line creates an in-line array of Object s that can be used to sort strings. The Arrays utility class then converts the array into a List . This is an efficient way to create a List , which can then sort data.
Once we have the array, we then use the Collections.sort() method. It modifies the target list and arranges the elements in their natural order. The resulting list then displays to the console.
Compare collection elements
So how do the generic sorting algorithms in Java compare elements in a type-independent way? The algorithms rely on the Comparable interface, which provides a single method, compareTo() :
public int compareTo (Object obj) returns:
A negative integer if this is less than obj
Zero if this and obj are equivalent
A positive integer if this is greater than obj
Classes that implement the Comparable interface can be compared with one another; this allows the sorting algorithms to arrange such elements in a list. As with the equals() method, you should only compare like-typed classes, otherwise a ClassCastException may be thrown. The standard Java data types (e.g., String , Integer ) all implement the Comparable interface to provide a natural sorting order.
To enable sorting, the String class implements the Comparable interface. To compare String s in a language-independent way, the String class implements the compareTo() method to provide a lexicographic ordering between strings. In other words, the strings are compared character by character, and the Unicode values determine whether the two strings are different:
"Aubergine".compareTo("Banana") < 0
"Banana" .compareTo("Aubergine") > 0
"Aubergine".compareTo("Aubergine") == 0
But beware?you might not always get exactly what you expect using natural ordering. The character-by-character comparison implementation is case sensitive and behaves oddly for accented characters. The Unicode character for A is 0x0041 , whereas the code for a is 0x0061 . There are also other accented variants for both, such as À , Á , à , and á , each with their own Unicode character value. Strings containing these characters can sort into different positions; because the character code for À is 0x00C0 , A < Z , while À > Z .
Implement Comparable
The Comparable interface provides a natural (i.e., default) sorting order for a class. We use an example Date class to demonstrate how sort order works:
public class Date implements Comparable {
private int year;
private int month;
private int day;
public Date(int year, int month, int day) {
this.year = year;
this.month = month;
this.day = day;
}
public int getYear() { return year; }
public int getMonth() { return month; }
public int getDay() { return day; }
public String toString() {
return year + "-" + month + "-" + day;
}
public int compareTo(Object o) throws ClassCastException {
Date d = (Date)o; // If this doesn't work, ClassCastException is thrown
int yd = year - d.year;
int md = month - d.month;
int dd = day - d.day;
if (yd != 0) return yd;
else if (md != 0) return md;
else return dd;
}
}
This class defines a data structure that contains three integers: year, month, and day. In the compareTo() method, we calculate the difference in year, month, and day. If the years are not the same ( yd!=0 ), then the method returns the difference in years. It will be negative if o < this , or positive otherwise. The same happens with the month. If the months are the same, then the method returns the difference in days.
Note: The return value does not have to be -1 , 0 , or 1 . Only the sign is important, not the value. In this case, the code just returns the difference in years, without worrying about the magnitude.
Create additional sort orderings
While the Comparable interface allows natural sorting order for a class, it is often desirable to sort data in a different order (such as reverse sorting or case-insensitive sorting). For example, sorting the list of String s [Aubergine, banana, aubergine, Banana] results in [Aubergine, Banana, aubergine, banana] , because the natural sorting order is a character-by-character comparison.
Although the String s' natural sorting order can't change, you can define an external sort on an existing class using the Comparator interface.
The Comparator interface defines the public int compare (Object o1, Object o2) method that returns:
A negative integer if o1 is less than o2
Zero if o1 and o2 are considered equivalent
A positive integer if o1 is greater than o2
To define a case-insensitive sorting operation for strings, we define the following class:
public class CaseInsensitiveComparator
implements java.util.Comparator {
public int compare(Object o1, Object o2) {
String s1 = o1.toString().toUpperCase();
String s2 = o2.toString().toUpperCase();
return s1.compareTo(s2);
}
}
To use the comparator, we pass an instance as the second argument to the Collections.sort() :
// Needs to import java.util.*;
Object[] data = {"Aubergine","banana","aubergine","Banana"};
List list = Arrays.asList(data);
Collections.sort(list, new CaseInsensitiveComparator() );
System.out.println(list);
// Displays [Aubergine, aubergine, banana, Banana]
The only difference between this code and the previous Collections.sort() code is the second argument to Collections.sort() . In this case, an instance of CaseInsensitiveComparator() is passed, which allows the comparison of List 's elements using CaseInsensitiveComparator() instead of the natural ordering provided by the String class's Comparable implementation. (Often, a comparator instance will be stored using the Singleton design pattern. This approach is shown in the downloadable code examples.)
Note: Because Aubergine and aubergine are considered equivalent (as are banana and Banana), they remain in the same relative order as they were before the sort. Sorting algorithms that preserve the order for otherwise equal e
Read
Tutorial at: Click here to view the tutorial
Rate Tutorial: Sort it
out
View Tutorial: Sort it
out
Related
Tutorials:
 Java Q&A - Java Still Open
Java Q&A - Java Still Open
|
Java Q&A, Open Java?
Java Q&A, Open Java?
|
Programming Java threads in the
real world, Part
4 - JavaWorld -
December 1998
Programming Java threads in the
real world, Part
4 - JavaWorld -
December 1998
|
Java memory management
Java memory management
|
Agents: Not just for Bond anymore - JavaWorld April
1997
Agents: Not just for Bond anymore - JavaWorld April
1997
|
Validation with Java and XML Schema, Part 2 - JavaWorld October 2000
Validation with Java and XML Schema, Part 2 - JavaWorld October 2000
|
Validation with Java and XML schema, Part 4 - JavaWorld December 2000
Validation with Java and XML schema, Part 4 - JavaWorld December 2000
|
Design for
performance, Part 1: Interfaces
matter - JavaWorld January
2001
Design for
performance, Part 1: Interfaces
matter - JavaWorld January
2001
|
J2ME: The next
major games
platform? - JavaWorld March 2001
J2ME: The next
major games
platform? - JavaWorld March 2001
|
Can double-checked locking be fixed? - JavaWorld May 2001
Can double-checked locking be fixed? - JavaWorld May 2001
|
Study guide Achieve strong performance with threads
Part 1
Study guide Achieve strong performance with threads
Part 1
|
Speed up your
Swing GUI construction with better building blocks
Speed up your
Swing GUI construction with better building blocks
|
Sort it
out
Sort it
out
|
The first taste of Liberty
The first taste of Liberty
|
Datastructures and algorithms, Part 1
Datastructures and algorithms, Part 1
|
confusing
title
confusing
title
|
good
design pattern
good
design pattern
|
Introducory
article
Introducory
article
|
Berkeley DB, Java Edition I: The Basics
The original version of Berkeley DB is written in C. This means that, up until now, if a Java programmer wanted to use Berkeley DB, she would have to use some sort of translation layer (for example, JNI) to handle the communication between Java and Berkel
|
Gain SQL SELECT functionality in Java
Gain SQL SELECT functionality in Java
Summary
In "Filter Collections," David Rappoport described a simple way to filter collections of objects. In this article, he expands on this idea and shows you how to treat an array or a collection of objects the s
|
|
|
|
