Java 101: Datastructures and algorithms in Java, Part 2

Searching and sorting one-dimensional arrays

1 2 3 Page 3
Page 3 of 3

Insertion Sort

The Insertion Sort algorithm orders a one-dimensional array of n data items into ascending order or descending order. An outer loop makes n-1 passes over the array. Each pass selects the next data item to be inserted into the appropriate position. It uses an inner loop to find this position, shifting data items to make room.

Insertion Sort begins by dividing the datastructure into sorted and unsorted sections. Initially, the sorted section contains the data item at index 0; the unsorted section contains all other data items. During the sort, each unsorted section data item is inserted into the proper position in the sorted section and the unsorted section shrinks by one data item.

Here is pseudocode for the Insertion Sort algorithm in a one-dimensional array of integers, where you are doing an ascending sort:


DECLARE INTEGER a, i, j
DECLARE INTEGER x[] = [ ... ]
FOR i = 1 TO LENGTH(x) - 1
   a = x[i]
   j = i
   WHILE j GT 0 AND x[j - 1] GT a
      x[j] = x[j - 1]
      j = j - 1
   END WHILE
   x[j] = a
NEXT i
END

Like Bubble Sort, Insertion Sort is fairly easy to understand. For example, consider a one-dimensional unordered array of four integers: [ 18, 16, 90, -3 ], where integer 18 is located at index 0 and integer -3 is located at index 3. When instructed to sort this array into ascending order, the algorithm performs the sort as follows:


i = 1                 i = 2                 i = 3
      =====                 =====                 =====
18 | 16   90   -3     16   18 | 90   -3     16   18   90 | -3     -3   16   18   90
     ^                          ^                          ^
     |                          |                          | 
     a,j                        a,j                        a,j

The sorted section appears on the left and initially consists of [ 18 ]. The unsorted section appears on the right and initially consists of [ 16, 90, -3 ].

Insertion Sort has a time complexity of O(n) comparisons for the best case (data is already sorted or nearly sorted) and O(n2) for the average and worst cases. The algorithm offers linear (best case) or quadratic (average/worst case) performance.

Listing 5 shows the source code for the InsertionSort application.

Listing 5. InsertionSort.java


{
   public static void main(String[] args)
   {
      // Validate command line arguments count.

      if (args.length != 1)
      {
         System.err.println("usage: java InsertionSort integers");
         return;
      }

      // Read integers from first command-line argument. Return if integers 
      // could not be read.

      int[] ints = readIntegers(args[0]);
      if (ints == null)
         return;

      // Output integer array's length and number of inversions statistics to
      // standard output device.

      System.out.println("N = " + ints.length);
      int inversions = 0;
      for (int i = 0; i < ints.length - 1; i++)
         for (int j = i + 1; j < ints.length; j++)
            if (ints[i] > ints[j])
               inversions++;
      System.out.println("I = " + inversions);

      // Output unsorted integer values to standard output, sort the array, 
      // and output sorted values to standard output.

      dump(ints);
      sort(ints);
      dump(ints);
   }

   static void dump(int[] a)
   {
      for (int i = 0; i < a.length; i++)
         System.out.print(a[i] + " ");
      System.out.print('\n');
   }

   static int[] readIntegers(String s)
   {
      String[] tokens = s.split(",");
      int[] integers = new int[tokens.length];
      for (int i = 0; i < tokens.length; i++)
         integers[i] = Integer.parseInt(tokens[i]);
      return integers;
    }

   static void sort(int[] x)
   {
      int j, a;

      // For all integer values except the leftmost value ...

      for (int i = 1; i < x.length; i++)
      {
         // Get integer value a.

         a = x[i];

         // Get index of a. This is the initial insert position, which is
         // used if a is larger than all values in the sorted section.

         j = i;

         // While values exist to the left of a's insert position and the
         // value immediately to the left of that insert position is
         // numerically greater than a's value ...

         while (j > 0 && x[j - 1] > a)
         {
            // Shift left value -- x[j - 1] -- one position to its right --
            // x[j].

            x[j] = x[j - 1];

            // Update insert position to shifted value's original position
            // (one position to the left).

            j--;
         }

         // Insert a at insert position (which is either the initial insert
         // position or the final insert position), where a is greater than
         // or equal to all values to its left.

         x[j] = a;
      }
   }
}

Compile Listing 5 as follows:

javac InsertionSort.java

Run the resulting application as follows:

java InsertionSort "18,16,90,-3"

You should observe the following output:


N = 4
I = 4
18 16 90 -3
-3 16 18 90

In conclusion

This article has introduced one-dimensional arrays, which are the simplest arrays. Part 3 will explore more complex arrays, namely multidimensional arrays and ragged arrays. I will also introduce the debate about whether an array is, or is not, a Java object. I will present my case that arrays are indeed objects in Java.

1 2 3 Page 3
Page 3 of 3