Sorting Basics

The Sorting Application

The examples in this document all part of the Java Application Sorting. Download the source archive Sorting.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Like others, the Sorting project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

The Java files from the project which are referenced in this document are:
demo/
  SortDemo
  ComparatorSort
  PersonSort
  StableSort

Sorting in Java

Sorting is one of the most common complex operations used. Database systems, for example, make use of sorting as a common method for data presentation to the user interface. Java provides two built-in ways to do sorting: The descriptions of these algorithms and their usage can be seen in the Java Data Structures (java.util) document in the Arrays and Collections sections, respectively.

For an array, A, of any primitive types or any Object type, these are supported:
Arrays.sort(A);
Arrays.sort(A, fromIndex, toIndex);
The Arrays.sort function also gives the ability to sort a range between two indices. The "toIndex" argument name is misleading since the sort range is really between fromIndex and toIndex – 1, inclusive. Thus these two calls are equivalent:
Arrays.sort(A);      is the same as       Arrays.sort(A, 0, A.length);
For a list, L, of Comparable elements, this is defined:
Collections.sort(L);
Java sorting also supports passing a comparator to be used for making comparisons between elements.

Sorting arrays via Arrays.sort

The Arrays.sort has many overloaded possibilities:
static void sort(byte[] a)
static void sort(char[] a)
static void sort(double[] a)
static void sort(float[] a)
static void sort(int[] a)
static void sort(long[] a)
static void sort(short[] a)
 
static void sort(byte[] a, int fromIndex, int toIndex)
static void sort(char[] a, int fromIndex, int toIndex)
static void sort(double[] a, int fromIndex, int toIndex)
static void sort(float[] a, int fromIndex, int toIndex)
static void sort(int[] a, int fromIndex, int toIndex)
static void sort(long[] a, int fromIndex, int toIndex)
static void sort(short[] a, int fromIndex, int toIndex)
 
static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex)
 
static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
There are two overarching differentiations: Taking that into consideration, there are three categories: The sort function for general Object types without a comparator are these:
static void Arrays.sort(Object[] a)
static void Arrays.sort(Object[] a, int fromIndex, int toIndex)
General in this means "any class" in the sense that Java simply assumes the the objects are comparable and makes this cast whenever it has to compare two array elements:
((Comparable)a[i]).compareTo(a[j])
Saying it another way, the Java array sort function will give a run time error when non-comparable elements are used instead of a compile time error.

For classes which are known to not be comparable, or for which we want to subvert the innate comparability, we need to pass a comparator:
static <T> void Arrays.sort(T[] a, Comparator<? super T> c)
static <T> void Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
The argument
Comparator<? super T> c
means that c is a comparator for the class itself, or for a superclass.

Collections.sort

There are only two versions of these static Collections.sort functions for sorting List objects: The type qualification used in the first case
<T extends Comparable<? super T>>
is Java's way of saying that "T must be a comparable type or the extension of one." In the case of Collections, Java gives a compile-time error on sorting Lists of non-comparable elements without a comparator.

Basics

Basic Demo

Use this main class to illustrate the sorting of an array or list of Integers using the natural order:
demo.SortDemo  

Using a comparator

This second example shows the sorting of an array or list of Integers using a comparator. The comparator makes the Integer comparsion like String comparison.
demo.ComparatorSort  

Sorting Variations

The intention of this example is to show variations on sorting objects of a class which is initially not comparable. Our choices are The program illustrates a fundamental difference between Arrays.sort and Collections.sort.
demo.PersonSort  

User-defined classes/Stability

This example illustrates how sorting can be done on any user-defined class whatsoever by defining a suitable comparator for the class. The class we define called Email has data values consisting of a String from and an Date time. This program illustrates sorting in two ways, based on these two fields.
demo.StableSort  
The output of this program looks like this:
----------------- before
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
----------------- sorted by time
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
----------------- sort by from
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008

Stable sort

In the above example, the first sort orders the entries by time, the second sort orders by name. The fact that the entries which have the same name are still ordered by time means that the sorting algorithm used by Java is stable.

A stable sorting algorithm is one in which equal element retain their same relative ordering. In our case, all the "bob" elements which were ordered by time are equal with respect to sorting by the from field, and they are still ordered by time afterwards.

Note that stability is only necessary for Java object types, not primitive types, because, obviously, equal primitive values all look the same!

This stability feature is implicitly used in virtually every User Interface program which allows the user to list elements according to different characteristics.


© Robert M. Kline