Sorting in Java - Part 1

Information on sorting algorithms can be found everywhere. Nevertheless, I would still include a section on this topic for the following reasons.

1. This is a programming blog. It looks "more complete" if it contains a section on sorting.
2. Something new can always be learned by looking at other people's source code. So why not have a look at how Macteki implements various sorting algorithms in Java ?

Sorting in Java - The Easy Way

The easiest way to sort in any programming language is, of course, using the language API if it is available. Therefore, let's start our journey with a simple API, java.util.Arrays.sort().

/******************************************************************************
* File : JavaSort.java
* Author : http://java.macteki.com/
* Description :
*   Demonstrate the use of java.util.Arrays.sort
* Tested with : JDK 1.6
******************************************************************************/

class JavaSort
{

  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }


  public static void main(String[] args) throws Exception
  {
    // array to be sorted
    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    java.util.Arrays.sort(a);   // sort using java API

    // print the sorted array    
    printArray(a);

  }
}

Descending Sort

The above sample sorts the integer array in ascending order. There are at least two ways to make a descending output using the same API. The first way is simple : use special indexing technique to change the order of output in the printArray() method.

// printArray in reverse order
  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      int reindex = a.length-i-1;
      System.out.print(delim+a[reindex]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }

This is a kind of "logical sorting". Physically we don't change the position of the elements in the array. But logically we sort it in descending order using a implied "index" array. You can create explicit index array if you wish, but that's just a waste of space in this simple example.

Descending Sort - Using customized Comparator

If you wish to sort the array physically, it is still possible to use the API. However, we need to pass an additional parameter to tell Java how to compare two elements.

java.util.Arrays.sort(a, new DescendingComparator());

We must implement the DescendingComparator. Here is a simple implementation.

class DescendingComparator implements java.util.Comparator<Integer>
{
  public int compare(Integer a,Integer b)
  {
    return b-a;
  }
}

According to the official documentations, we must implements the compare method such that it has the following properties :

1. It must return a negative value if element a is logically smaller than element b
2. It must return a positive value if element a is logically bigger than element b
3. It must return zero if element a is logically equal to element b

Note the term "logically". For example, 5 is physically greater than 3, but in our logical order (descending order), it is smaller than 3, smaller in the sense of its logical position, not in the sense of its value.

Full sample given below.

/******************************************************************************
* File : DescendingSort.java
* Author : http://java.macteki.com/
* Description :
*   Demonstrate the use of java.util.Arrays.sort with a customized Comparator
* Tested with : JDK 1.6
******************************************************************************/

class DescendingSort
{

  public static void printArray(Integer[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }


  public static void main(String[] args) throws Exception
  {
    Integer[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};

    java.util.Arrays.sort(a, new DescendingComparator());
    
    printArray(a);

  }
}

// Use a separate source file if you wish.
class DescendingComparator implements java.util.Comparator<Integer>
{
  public int compare(Integer a,Integer b)
  {
    return b-a;
  }
}

Next

Some simple sorting algorithms in Java will be presented in the next article.