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]

Resizing an array

An array can’t be resized. You will have to create a larger temporary array,
copy the values and have the original array point to the temporary one.
Take a look at the collection classes to use as an alternative for arrays.

Following app demonstrates the use:

public class Main
{
   public static void main(String args[]) {
      int []values = { 1, 2, 3, 4, 5, 6 };
 
      System.out.println("Before:");
      printArray(values);      
 
      // double the size
      int []temp = new int[values.length * 2];
      System.arraycopy(values, 0, temp, 0, values.length);
      values = temp;
 
      System.out.println("After:");
      printArray(values);      
   }
 
   public static void printArray(int []array) {
      for (int i=0; i<array.length; i++) {
         System.out.print(array[i] + " ");
      }
      System.out.println();
   }
}

outputs:

Before:
1 2 3 4 5 6 
After:
1 2 3 4 5 6 0 0 0 0 0 0

Fast copying an array

There is a fast native method available in the java.lang.System class: arraycopy().
It can be used to copy a region of one array to another. If an array of objects
is copied, only the references are copied. arraycopy() does not allocate memory
for the destination array. Make sure you have allocated enough memory for the
destination array to hold the copied region.

This is its signature:
arraycopy(Object src, int srcOffset, Object dst, int dstOffset, int count)

Following example demonstrates the use:

public class Main
{
   public static void main(String []args) {
      int [] src = { 1, 2, 3, 4, 5, 6, 7, 8 };
      int [] dst = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
      System.arraycopy(src, 2, dst, 1, 3);
   
      printArray(src);
      printArray(dst); 
   }
 
   public static void printArray(int []array) {
      for (int i=0; i<array.length; i++) {
         System.out.print(array[i] + " ");
      }
      System.out.println();
   }
}

outputs:

1 2 3 4 5 6 7 8 
0 3 4 5 0 0 0 0 

Creating multi-dimensional arrays

Examine the following double array:

      double ar[][] = 
        { { 20.0 },
          { 20.0, 19 },
          { 20.0, 19.0, 18.0 },
          { 20.0, 19.0, 18.0, 17.0 },
          { 20.0, 19.0, 18.0, 17.0, 16.0 } };

You can achieve the same setup dynamically by looping through the row indices and dynamically creating a array with variable length:

public class Main {
   public static void main(String []args) {
      double ar[][] = null;
 
      ar = new double[5][];
      for (int i=0; i<ar.length; i++) {
         ar[i] = new double[i+1];
         for (int j=0; j<i+1; j++) {
            ar[i][j] = (double) 20 - j;
         }
      }
 
      for (int i=0; i<ar.length; i++) {
         for (int j=0; j<ar[i].length; j++) {
            System.out.print(ar[i][j] + " ");
         }
         System.out.println();
      }
   }
}

Converting a hexadecimal (hex), octal, or binary value to an integer

Use the static method parseInt in the Integer primitive wrapper class. You pass in a string containing the digits of the specified radix. If a digit is not in the radix range, you’ll get a NumberFormatException.

Here’s an example:

public class Main
{
   public static void main(String args[]) {      
      // convert from hexadecimal                
      int a = Integer.parseInt("FF1C", 16);
  
      // convert from octal
      int b = Integer.parseInt("107", 8);
 
      // convert from binary
      int c = Integer.parseInt("10010", 2);
 
      System.out.println(a);   // 65308
      System.out.println(b);   // 71
      System.out.println(c);   // 18
   }
}