Sorting Arrays

Natural Ordering

All built-in types have what is called a "natural ordering", which is the obvious numeric ascending ordering
Objects have a natural ordering if they come from a class that implements the Comparable interface
- This "natural ordering" is specified by the overridden compareTo() method

class `Arrays`

class java.util.Arrays is a utility class that contains various methods for manipulating arrays, including sorting and searching

There are a number of sort() methods for sorting arrays of built-in types
To sort an array of objects, using the "natural ordering":
- Just use the method: void sort(Object[])
- Your object type must implement Comparable
To sort an array of objects using some other custom ordering (i.e. not the "natural ordering"):
- Can use the method: void sort(Object[], Comparator)
- This means you have to implement the Comparator interface and override the "int compare(Object, Object)" method, to specify your ordering rule
- An object implementing the Comparator interface is passed as the second parameter to this sort method
- Can do this with a regular class, an inner class, or an anonymous inner class

Example

Here's a program that sorts a list of names (Strings) in various ways. There are various versions that illustrate the use of interfaces, nested classes, and anonymous inner classes.

Sorting1.java - Uses generics (since Java 1.5), with separate classes
Sorting2.java - Uses generics, and private static nested classes for building new comparison rules (with Comparator interface)
Sorting2Old.java - What the previous example looked like, before generics (Java 1.4.2)
SortingAnon.java - A version that uses anonymous inner classes for building the extra sorting rules

Here's the code of Sorting2.java, using nested classes, along with sample output listed below:

// Sorting2.java
// 
// This version uses the Comparator<T> interface (using generics)
//  but implements the interface with static nested classes (with names)


import java.util.*;

// Example of how to sort an array several different ways
public class Sorting2
{
    static String[] nameArray = {"Bob", "Fred", "Ralph", "Joe", "Wanda", 
                                 "Joanna", "billy Joe", "jennifer", "John"};

    public static void main(String[] args)
    {
        // print the original unsorted array
        System.out.println("");
        printRuleAndArray("Original name list:");

        // sorting by 'natural ordering'
        Arrays.sort(nameArray);
        printRuleAndArray("Sorted by 'natural ordering' " +
                                 "(lexicographic):");

        // sorting by length
        Arrays.sort(nameArray, new LengthCompare());

        printRuleAndArray("Sorted list by name length:");

        // sorting alphabetically
        Arrays.sort(nameArray, new AlphaCompare());

        printRuleAndArray("Sorted list in alphabetical order:");

        // sorting lexicographically by last letter 
        Arrays.sort(nameArray, new LastLetterCompare());

        printRuleAndArray("Sorted list in lexicographic order " +
                                 "of last letter:");
    }

    static void printRuleAndArray(String rule)
    {
        System.out.println(rule);
        for (int i = 0; i < nameArray.length; i++)
        {
            System.out.println(nameArray[i]);
        }
        System.out.println("");
    }


 // implement Comparator to compare Strings by length
 private static class LengthCompare implements Comparator<String>
 {
   public int compare(String s1, String s2)
   {
      return (s1.length() - s2.length());
   }
 }

 // implement Comparator to compare Strings alphabetically
 private static class AlphaCompare implements Comparator<String>
 {
   public int compare(String s1, String s2)
   {
      return (s1.toLowerCase().compareTo(s2.toLowerCase()));
   }
 }


 // implement Comparator to compare Strings by last letter
 private static class LastLetterCompare implements Comparator<String>
 {
   public int compare(String s1, String s2)
   {
       return(s1.charAt(s1.length() - 1) 
	    - s2.charAt(s2.length() - 1) );
   }
 }

}      // end of class Sorting2

Output from this example program

Original name list:
Bob
Fred
Ralph
Joe
Wanda
Joanna
billy Joe
jennifer
John

Sorted by 'natural ordering' (lexicographic):
Bob
Fred
Joanna
Joe
John
Ralph
Wanda
billy Joe
jennifer

Sorted list by name length:
Bob
Joe
Fred
John
Ralph
Wanda
Joanna
jennifer
billy Joe

Sorted list in alphabetical order:
billy Joe
Bob
Fred
jennifer
Joanna
Joe
John
Ralph
Wanda

Sorted list in lexicographic order of last letter:
Joanna
Wanda
Bob
Fred
billy Joe
Joe
Ralph
John
jennifer

Sorting Arrays

Natural Ordering

class Arrays

Example

Output from this example program

class `Arrays`