Sorting Data with Java Collections

Sorting data with Java Collections: introduction

Here, 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 order;
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...

We will 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.

How to sort a list(a simple object type) of Strings or Integers in Java -

Following on from our introduction to sorting in Java, we consider here one of the simplest cases of sorting a List of simple objects such as Strings or Integers. Let's say we have a simple list of Strings:

List words = new ArrayList(50);
words.add("once");
words.add("upon");
words.add("a");
words.add("time");
...

Now, we can sort this list with a simple call to the following library method:

Collections.sort(words);

The Collections.sort() method will work "out of the can" on lists of various "basic" objects that you'd expect to be able to sort, including instances of Number– the primitive wrapper classes Integer, Long, Float etc plus BigInteger and BigDecimal.

Sorting an array

Sorting an array of these objects is just as easy(Refer point 1 as well at bottom of this post):

Arrays.sort(myArray);

The above method takes an array of objects, but the Arrays class also provides similar methods for sorting primitive arrays.

Next: other issues

What we've seen above is that sorting simple objects in Java such as numbers or strings is generally dead simple. But there are a couple more issues to deal with on the following pages:

What if we want to sort a different type of object, such as one that we've created? For this, we need to look at how to use the Java Comparable interface.
What if we want to control the ordering of a specific type of sort, even if the objects in question are 'naturally sortable'? For example, we might want to perform a case insensitive sort on Strings, or perform a "proper" alphabetic sort that takes account of things like the correct ordering of accents in non-English strings. For this, we need to look at Java Comparators.
In some cases, we may need to consider the performance of the Java sort algorithm: in particular, where we are repeatedly sorting very small lists, a simpler (even if less scalable) algorithm may work better.

Note:

1. In fact, the Collections.sort() method copies the list into an array and calls the Arrays.sort() method before copying the elements back into the list.

Performance of the Java Sorting algorithm -

1. Reading 1
2. Reading 2