Sorting data with Java Collections: introduction
On this and the following pages, we will look at how to sort data in Java. To start off
with, we'll assume that the problem we have is the following:
- we have a List or array of Java objects that is
(possibly) out of order1;
- we want to sort this list or array as a "one-off" action.
By "one-off", we mean that we don't need to keep the list permanently in order
as we add and remove elements, though Java does also provide 'permanently sorted' structures
if that is what we require.
But generally, sorting a list or array can be broken down into two problems:
- given any two of the objects that you want to sort (e.g. two Strings if
you're sorting a list of string data), how do you determine
the correct order of the two elements?;
- given the ability to determine the order of two elements, how do you construct
a sorting algorithm to sort an entire list of data?
Strictly speaking, these problems aren't totally separate, because some algorithms
rely on us being able to measure how far apart two items are.
But for sorting in Java, we can generally see the problem in the above two
stages. And in fact, for most practical purposes:
- Java already provides a good enough solution to the second problem;
- for many objects that have an obvious "natural ordering" (e.g. Integers,
Floats, Strings), Java also provides a solution to the first problem.
In other words, for the simplest case of sorting a list of Strings or
Integers (among other 'simple' objects), Java provides a one-line solution.
Where to go next...
On the next pages, we look at:
- how to sort a list of Strings and other "simple" objects in Java;
- how to let Java sort arbitrary objects of your own class, by
implementing the Comparable interface;
- how to specify your own sort order (whether the objects in question are 'naturally' sortable
or not) using Java's Comparator interface;
- Java sort performance: we look
at the performance behaviour of the built-in sort algorithm, which is useful to
know in some circumstances.
1. Actually, most of what we discuss will apply to sorting an array
of primitives too.