|
|
Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs
Have 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 Lists, how to provide sorting orders for data classes, and how to use a generic mechanism for sorting JavaBeans.
This article specifically covers:
Comparable interface provides a natural sorting order and how to sort a list of Strings into lexicographical order
Comparator interface and how a generic JavaBeans sorting mechanism sorts arbitrary JavaBeans with BeanPropertyComparatorCompositeComparatorDownload the source code associated with this article from Resources.
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.