Java 101: Datastructures and algorithms in Java, Part 2

Searching and sorting one-dimensional arrays

1 2 3 Page 2
Page 2 of 3

Binary Search has a time complexity of O(log2n), which is pronounced "Big Oh of log n to the base 2." For n data items, Binary Search requires a maximum of 1+log2n comparisons, making this algorithm vastly more efficient than Linear Search, in most cases. The algorithm offers logarithmic performance (for more about logarithmic performance, see Figure 3 in Part 1 of this series).

Listing 2 is a BinarySearch Java application that lets you experiment with Binary Search.

Listing 2. BinarySearch.java


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

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

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

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

      // Read search integer; NumberFormatException is thrown if the integer
      // isn't valid.

      int srchint = Integer.parseInt(args[1]);

      // Perform the search and output the result.

      System.out.println(srchint + (search(ints, srchint) ? " found"
                                                          : " not found"));
   }

   private 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;
   }

   private static boolean search(int[] x, int srchint)
   {
     int hiIndex = x.length - 1, loIndex = 0, midIndex;

      while (loIndex <= hiIndex)
      {
         midIndex = (loIndex + hiIndex) / 2;
         if (srchint > x[midIndex])
            loIndex = midIndex + 1;
         else
         if (srchint < x[midIndex])
            hiIndex = midIndex - 1;
         else
            return true;
      }

      return false;
   }
}

The BinarySearch application reads a comma-separated list of integers from its first command-line argument. It searches the array for the integer identified by the second command-line argument, and outputs a found/not found message.

To explore the Binary Search algorithm, do the following:

Compile the code in Listing 2 as follows:


javac BinarySearch.java

Run the resulting application as follows:


java BinarySearch "4,5,8" 5

You should observe the following output:


5 found

Run the resulting application a second time, as follows:


java BinarySearch "4,5,8" 15

You should observe the following output:


15 not found

Bubble Sort

The Bubble Sort algorithm orders a one-dimensional array of n data items into ascending or descending order. An outer loop makes n-1 passes over the array. Each pass uses an inner loop to exchange data items such that the next smallest (ascending sort) or largest (descending sort) data item "bubbles" toward the beginning of the array.

The "bubbling" action occurs in the inner loop, where each iteration compares the pass-numbered data item with each successive data item. If a successor data item is smaller (ascending sort) or larger (descending sort) than the pass-numbered data item, the successor data item is exchanged with the pass-numbered data item.

Here is pseudocode representing Bubble Sort in a one-dimensional array of integers/ascending sort context:


DECLARE INTEGER i, pass
DECLARE INTEGER x[] = [ ... ]
FOR pass = 0 TO LENGTH(x) - 2
   FOR i = LENGTH(x) - 1 DOWNTO pass + 1
      IF x[i] LT x[pass] THEN // switch to > for descending sort
         EXCHANGE x[i], x[pass]
      END IF
   NEXT i
NEXT pass
END

Bubble 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 requested to sort this array into ascending order, Bubble Sort would execute as follows:


Pass 0               Pass 1               Pass 2
======               ======               ======
18  16  90  -3       -3  16  90  18       -3  16  90  18
^           ^            ^       ^                ^   ^
|           |            |       |                |   |
-------------            ---------                -----
-3  16  90  18       -3  16  90  18       -3  16  18  90
^       ^                ^   ^ 
|       |                |   |
---------                -----
-3  16  90  18       -3  16  90  18
^   ^
|   |
-----
-3  16  90  18

In terms of comparisons and also in terms of exchanges, Bubble Sort has a time complexity of O(n2), which is pronounced "Big Oh of n squared." Bubble Sort offers quadratic performance, which isn't a problem for shorter-length arrays--especially when you consider that Bubble Sort is easy to code. (See Part 1 for more about quadratic performance.)

The BubbleSort Java application in Listing lets you experiment with Bubble Sort.

Listing 3. BubbleSort.java


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

      if (args.length != 1)
      {
         System.err.println("usage: java BubbleSort 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)
   {
      for (int pass = 0; pass < x.length - 1; pass++)
         for (int i = x.length - 1; i > pass; i--)
            if (x[i] < x[pass])
            {
               int temp = x[i];
               x[i] = x[pass];
               x[pass] = temp;
            }
   }
}

BubbleSort reads a comma-separated list of integers from its command-line argument. It outputs the array length, calculates and outputs the number of inversions (larger items to the left of smaller items in the unsorted array), outputs the unsorted array, sorts the array, and outputs the sorted array. (Selection Sort and Insertion Sort, which I'll introduce next, behave similarly.)

Compile Listing 3 as follows:


javac BubbleSort.java

Run the resulting application as follows:


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

You should observe the following output:


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

Selection Sort

The Selection 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 uses an inner loop to find the next smallest (ascending sort) or largest (descending sort) data item, which is exchanged with the pass-numbered data item.

Selection Sort assumes that the data item at the pass-numbered index is the smallest (ascending sort) or the largest (descending sort) of the remaining data items. It searches the rest of the array for a data item that's smaller/larger than this data item, and performs an exchange at the end of the search when a smaller/larger data item is found.

The following pseudocode expresses Selection Sort in a one-dimensional array of integers/ascending sort context:


DECLARE INTEGER i, min, pass
DECLARE INTEGER x[] = [ ... ]
FOR pass = 0 TO LENGTH(x) - 2
   min = pass
   FOR i = pass + 1 TO LENGTH(x) - 1
      IF x[i] LT x[min] THEN
         min = i
      END IF
   NEXT i
   IF min NE pass THEN
      EXCHANGE x[min], x[pass]
   END IF
NEXT pass
END

Selection 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 requested to sort this array into ascending order, the Selection Sort pseudocode performs the sort as follows:


Pass 0                        Pass 1                        Pass 2
======                        ======                        ======
18  16  90  -3                -3  16  90  18                -3  16  90  18
^                                 ^                                 ^
|                                 |                                 |
min = 0                           min = 1                           min = 2

18  16  90  -3                -3  16  90  18                -3  16  90  18
    ^                                 ^                                 ^
    |                                 |                                 |
    16 < 18, min = 1                  90 > 16, min = 1                  18 < 90, min = 3
                                                                    ^   ^
18  16  90  -3                -3  16  90  18                        |   |
        ^                                 ^                         -----
        |                                 |                 -3  16  18  90
        90 > 16, min = 1                  18 > 16, min = 1

18  16  90  -3                               
            ^   
            |
            -3 < 16 min = 3
^           ^
|           |
------------- 
-3  16  90  18

Selection Sort has a time complexity of O(n2) comparisons and O(n) exchanges. The algorithm offers quadratic performance in terms of comparisons and linear performance in terms of exchanges, which makes it somewhat more efficient than Bubble Sort.

Listing 4 shows the SelectionSort application in Java code.

Listing 4. SelectionSort.java


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

      if (args.length != 1)
      {
         System.err.println("usage: java SelectionSort 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)
   {
      for (int pass = 0; pass < x.length - 1; pass++)
      {
         int min = pass;

         for (int i = pass + 1; i < x.length; i++)
            if (x[i] < x[min])
               min = i;

         if (min != pass)
         {
            int temp = x[min];
            x[min] = x[pass];
            x[pass] = temp;
         }
      }
   }
}

Compile Listing 4 as follows:


javac SelectionSort.java

Run the resulting application as follows:


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

You should observe the following output:


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

1 2 3 Page 2
Page 2 of 3