Java Notes

Sorting Arrays

Why you shouldn't write your own sort

Good student problem. A favorite computer science topic it sorting, putting a collection of data in some order. Typically this is done for arrays. Textbooks cover both the slow, O(n²), sorts (eg, selection, insertion, and bubble sorts) and fast, O(n log n), sorts (quick sort, heap sort, etc). These are interesting problems, give students a lot of practice with arrays, bring up important tradeoffs, and are generally quite educational.

Bad professional pratice. However, the Java library already has sort methods that are more efficient, more general, and more correct than anything you are likely to write yourself. And they are already written. Professional programmers use one of the java.util.Arrays.sort() methods; they do not write their own, except perhaps in unusual cases.

Other data structures. There are sort methods in the java.util.Collections class which can be used to sort other kinds of data structures (eg, ArrayList), and there are data structures such as TreeMap that keep elements sorted based on a key.

Sorting Arrays with `Arrays.sort(...)`

The java.util.Arrays class has static methods for sorting arrays, both arrays of primitive types and object types. The sort method can be applied to entire arrays, or only a particular range. For object types you can supply a comparator to define how the sort should be performed.

Method	Description
Arrays sort methods
`Arrays.sort(pa);`	Sorts the elements of the array of a primitive type into ascending order using their natural ordering.
`Arrays.sort(pa, from, to);`	Sorts the elements pa[from]...pa[to-1] of a primitive type. into ascending order.
`Arrays.sort(oa);`	Sorts the elements of the array of an object type into ascending order, using the order defined by `Comparable` interface, which defines the `compareTo` method. Note that many Java classes such as `String` (but not `StringBuffer`), `Double`, `BigInteger`, etc implement `Comparable`.
`Arrays.sort(oa, from, to);`	Sorts the elements of the array, in the range from...to of an object type into ascending order.
`Arrays.sort(oa, comp);`	Sorts the elements of the array of an object type into ascending order, using the Comparator comp.
`Arrays.sort(oa, from, to, comp);`	Sorts the elements of the array, in the range from...to of an object type into ascending order using the Comparator comp.

Example - Sorting arrays using Arrays.sort()

This example sorts an array of Strings and an array of doubles. All object types that implement Comparable (ie, defines compareTo() method), can be sorted with using a comparator. The Arrays.sort() method is also defined for primitive arrays.

// File   : data-arrays/dblsort/Dblsrt.java
// Purpose: To show how Arrays.sort() works with arrays
//          of both primitive and object values.
// Author : Fred Swartz 2006-08-23.  Public domain.

import java.util.Arrays;

public class Dblsrt {
    //========================================================= main
    public static void main(String[] args) {
        //... 1. Sort strings - or any other Comparable objects.
        String[] names = {"Zoe", "Alison", "David"};
        Arrays.sort(names);
        System.out.println(Arrays.toString(names));

        //... 2. Sort doubles or other primitives.
        double[] lengths = {120.0, 0.5, 0.0, 999.0, 77.3};
        Arrays.sort(lengths);
        System.out.println(Arrays.toString(lengths));
    }
}

Output from above program

[Alison, David, Zoe]
[0.0, 0.5, 77.3, 120.0, 999.0]

Comparators can define sort order

Java uses comparison sorts, which means that they make all ordering decisions by comparing two values. If there is no "natural" ordering, or you don't want to use it, you can specify a Comparator to use in comparing two values. See Comparators.

Sorting ArrayLists using `Collections.sort(...)`

In a similar way, you can use the methods below to sort ArrayLists.

   Collections.sort(alist);
   Collections.sort(alist, comparator);