Sorting an array

Since JDK1.2, the utility class Arrays in the java.util package provides useful
array manipulation methods such as fill, binary search and sort.
A fast algorithm to sort an unsorted array is QuickSort. It provides you with
O(n*log(n)) time complexity, where n is the number of entries to sort. If you
execute the quicksort algorithm on sorted arrays, it performs very badly (O(n^2)),
a linear sort would do a better job in that case. The sort method of Arrays is based
on a modified quicksort algorithm so that it doesn’t degrade for many datasets
that would cause a normal quicksort to do so.

The method sort is defined for arrays of type byte[], char[], double[], float[], int[],
long[], object[].

Following example demonstrates the use of sort:

import java.util.Arrays;
 
public class Main
{
   public static void main(String args[]) {
      int values[] = { 5, 74, 23, 99, 6, 0, -2, -60 };
 
      System.out.println("Unsorted array:");
      printArray(values);
 
      Arrays.sort(values);
 
      System.out.println("Sorted array:");
      printArray(values);
   }
 
   public static void printArray(int []values) {
      for (int i=0; i<values.length; i++) {
         System.out.print(values[i] + " ");
      }
      System.out.println();
      System.out.println();
   }
}

outputs:

Unsorted array:
5 74 23 99 6 0 -2 -60 
 
Sorted array:
-60 -2 0 5 6 23 74 99 

You can just as easily sort an array of user-defined objects. The only catch
is that you will have to define a comparator to tell the method whether object
A is less than, equal or bigger than object B.
Here’s an example:
RedColorComparator is introduced, a Comparator that only takes into account the red value of
the RGB value.

import java.util.Comparator;
import java.util.Arrays;
import java.awt.Color;
 
public class Main
{
   public static void main(String []args) {
      Color colArr[] = { new Color(43, 100, 100), new Color(170, 59, 255),
                         new Color(0, 0, 0),      new Color(220, 220, 220),
                         new Color(10, 255, 255), new Color(255, 0, 0) };
 
      System.out.println("Unsorted array:");
      printArray(colArr);
 
      Arrays.sort(colArr, new RedColorComparator());
 
      System.out.println("Sorted array:");
      printArray(colArr);
   }
 
   public static void printArray(Color colArr[]) {
      for (int i=0; i<colArr.length; i++) 
         System.out.println(colArr[i]);
      System.out.println();
   }
}
 
class RedColorComparator implements Comparator
{
   public int compare(Object o1, Object o2) {
      int red1 = ((Color) o1).getRed();
      int red2 = ((Color) o2).getRed();
      return (new Integer(red1)).compareTo(new Integer(red2));
   } 
}

outputs:

Unsorted array:
java.awt.Color[r=43,g=100,b=100]
java.awt.Color[r=170,g=59,b=255]
java.awt.Color[r=0,g=0,b=0]
java.awt.Color[r=220,g=220,b=220]
java.awt.Color[r=10,g=255,b=255]
java.awt.Color[r=255,g=0,b=0]
 
Sorted array:
java.awt.Color[r=0,g=0,b=0]
java.awt.Color[r=10,g=255,b=255]
java.awt.Color[r=43,g=100,b=100]
java.awt.Color[r=170,g=59,b=255]
java.awt.Color[r=220,g=220,b=220]
java.awt.Color[r=255,g=0,b=0]