Java Sorting

Java Sorting
(last updated: Feb 6, 2006)

. The Java Collections class supports a number of useful operations on Java data structures. Many of these operations are targetted to work on List objects. The Java List (java.util.List) is actually an interface. Our typical implementation is ArrayList. The Vector class is also a common choice for List implementation but it is less preferable unless there is specific need for thread-safe (i.e., synchronized) operations which incur additional overhead.

You have to be careful in GUI applications which use java.util.List because of the existence of another List class: java.awt.List. For example, a Java program which uses these imports:

import java.util.*;
import java.awt.*;

will cause a statement like this:

List mylist;

to be ambiguous. To resolve the ambiguity, use the fully qualified class name:

java.util.List mylist = ...

Generics

Once a list object is created, sorting is most easily done using the operation:

Collections.sort(list);

As of Java 1.5, a List should be declared as generic (template) class in which we specify the type of the elements in the list. Here is an example:




SortTest1.java


import java.util.*;

class SortTest1 {
  public static void main( String[] args ) {
    Random r = new Random();
    List<Integer> list = new ArrayList<Integer>();

    for(int i=0; i < 10; ++i)
      list.add( new Integer(r.nextInt() % 100) );

    System.out.print( "the list: " ); System.out.println( list );
    Collections.sort( list );
    System.out.print( "sorted:   " ); System.out.println( list );
  }
}

Comparable objects

Sorting of objects of a class will work directly, as above, as long as the class is Comparable. In Java terms, this means that the class must implement the (generic) interface:

java.lang.Comparable<T>

and thereby define the single function

public int compareTo( T o )

with this interpretation:

o1 is "less than" o2    if o1.compareTo(o2) < 0
o1 is "equal to" o2     if o1.compareTo(o2) = 0
o1 is "greater than" o2 if o1.compareTo(o2) > 0

All the predefined Java classes that you would imagine to be comparable, such as String, Integer, Float, Long, java.util.Date, etc. do indeed implement this interface. This sample program illustrates the direct usage of compareTo:




ComparableTest.java


import java.util.*;

class ComparableTest
{
  public static void main( String[] args )
  {
    Integer x = new Integer(1), y = new Integer(5), z = new Integer(5);

    System.out.println( x + ".compareTo(" + y + ") = " + x.compareTo(y) );
    System.out.println( y + ".compareTo(" + x + ") = " + y.compareTo(x) );
    System.out.println( y + ".compareTo(" + z + ") = " + y.compareTo(z) );
    System.out.println( "-----------------" );

    String s = "1111", t = "22";

    System.out.println( s + ".compareTo(" + t + ") = " + s.compareTo(t) );
    System.out.println( t + ".compareTo(" + s + ") = " + t.compareTo(s) );
  }
}

whose execution looks like this:

1.compareTo(5) = -1
5.compareTo(1) = 1
5.compareTo(5) = 0
-----------------
1111.compareTo(22) = -1
22.compareTo(1111) = 1

User-defined comparable objects

For a user-defined class to be sorted as above, we must make it implement the Comparable interface, meaning that we have to define a compareTo function, defining the relationship between any two object (less than, equals, or greater than). Here is an example:




MyClass.java


public class MyClass implements Comparable<MyClass> {
  public String x;
  public int y;
  public MyClass(String x, int y) { this.x = x; this.y = y; }
  public int compareTo(MyClass c) { return y - c.y; }
  public String toString() { return "<" + x + "," + y + ">"; }
}

Using this class definition, we can sort a list of MyClass objects as in this example:




SortTest2.java


import java.util.*;

class SortTest2 {
  public static void main( String[] args ) {
    MyClass[] array = {
      new MyClass("t", 16),
      new MyClass("r", 9),
      new MyClass("i", 16),
      new MyClass("s", -3), 
      new MyClass("o", 2),
      new MyClass("g", 25),
      new MyClass("n", 16),
    };

    List<MyClass> list = new ArrayList<MyClass>();
	 
    for (MyClass x: array) { list.add(x); }
	     
    System.out.print( "the list: " ); System.out.println( list );
    Collections.sort( list );
    System.out.print( "sorted:   " ); System.out.println( list );
  }
}

whose execution looks like this:

the list: [<t,16>, <r,9>, <i,16>, <s,-3>, <o,2>, <g,25>, <n,16>]
sorted:   [<s,-3>, <o,2>, <r,9>, <t,16>, <i,16>, <n,16>, <g,25>]

The output illustrates a feature of the sorting algorithm. All three elements with second coordinate "2" are equal according to the compareTo function. Observe that they retain their original relative order in the sorted array. This is an intentional feature of the sorting algorithm called stability which permits a useful sort on multiple keys with multiple passes of sort.

In order to achieve this stability along with an O(n * log n) speed, the heapsort algorithm is a good candidate, in contrast the faster, unstable quicksort algorithm.

Sorting with Comparators

An alternative approach to sorting any type of object, comparable or not, is to use an explicit comparator object to provide the comparisons. In Java terms a comparator object is an object which implements the interface:

java.lang.Comparator<T>

and thereby define the single function:

public int compare( T o1, T o2 )

Once we have created such a comparator, comp, for the class T, we can sort a List<T> object, list, using the function call:

Collections.sort(list,comp);

Sorting with a comparator allows you to effectively ignore the built-in comparable properties of objects (whether they implement Comparable or not). Here is an example of a comparator which we can use for MyClass which compares according to the x coordinate in contrast to the built-in comparability according to the y coordinate.




MyClassComparator.java


import java.util.*;

class MyClassComparator implements Comparator<MyClass> {
  public int compare(MyClass c1, MyClass c2) { 
    return (c1.x).compareTo(c2.x); 
  }
}

Using this comparator class definition, we can sort the same list of MyClass objects as in this example:




SortTest3.java


import java.util.*;

class SortTest3 {
  public static void main( String[] args ) {
    /* create the same list as in SortTest2 */

    System.out.print( "the list: " ); System.out.println( list );
    Collections.sort( list, new MyClassComparator() );
    System.out.print( "sorted:   " ); System.out.println( list );
  }
}

whose execution looks like this:

the list: [<t,16>, <r,9>, <i,16>, <s,-3>, <o,2>, <g,25>, <n,16>]
sorted:   [<g,25>, <i,16>, <n,16>, <o,2>, <r,9>, <s,-3>, <t,16>]

Java Sorting(last updated: Feb 6, 2006)

Generics

Comparable objects

User-defined comparable objects

Sorting with Comparators

Java Sorting
(last updated: Feb 6, 2006)