4. Searching, Sorting and Recursion

What We Will Cover

Illuminations

Programming Style

Homework Questions?

Viewing WebCT Assignment Results and Solutions

Questions from last class?

^ top

4.1: Programming With Arrays

Objectives

At the end of the lesson the student will be able to:

  • Compute statistics on arrays of data
  • Search an array
  • Sort an array
  • Choose the best algorithm for searching an array

^ top

4.1.1: Partially-Filled Arrays

  • Arrays contain lists of items
  • May only have part of the list entered into an array
  • Consider the case of reading user input into an array
import java.io.*;

public class ArrayInput {
    public static void main(String [] args)
            throws IOException {
        BufferedReader in = new BufferedReader(
                new InputStreamReader(System.in));

        System.out.print("How many integers? ");
        String line = in.readLine();
        int numItems = Integer.parseInt(line);
        int[] data = new int[numItems];

        for (int i = 0; i < data.length; i++) {
            System.out.print("Enter item #" + i + ": ");
            line = in.readLine();
            data[i] = Integer.parseInt(line);
        }

        System.out.print("\nYou entered: ");
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + ", ");
        }
        System.out.println("\n");
    }
}
  • What does the data array contain before the user enters any values?
  • How do we know how many items have been entered by the user?
  • What is the value of data.length after one item has been entered?

    • Note:

  • There is no automatic mechanism to detect how many items have been entered
  • Programmer must keep track of the progress

^ top

4.1.2: Summing an Array

  • Can use a loop to examine every item in an array
    • public class ArraySum{
    public static void main(String [] args) {
        int[] data = {1, 2, 3, 4, 5};
        int sum = 0;
        for (int i = 0; i < data.length; i++) {
            sum = sum + data[i];
            System.out.print(data[i] + ", ");
        }
        System.out.println("\nsum = " + sum);
    }
}
  • What code would we add to show the average of the array values?
  • What would we change to find the maximum array value?
  • How would we find the minimum array value?
  • What is the easiest way to initialize minimum and maximum values?

Minimum and Maximum int Values

  • Remember that int types can only hold a range of values
  • Maximum value given by Integer.MAX_VALUE
  • Minimum value given by Integer.MIN_VALUE
  • Using Integer.MAX_VALUE and Integer.MIN_VALUE is not the easiest way to initialize minimum and maximum values

^ top

4.1.3: Searching an Array

  • Many techniques for searching an array for a particular value
  • Sequential search:
    • Start at the beginning of the array
    • Compare each value in sequence
    • If value is found, then exit
    • Continue until you reach the end of the array
    class ArrayFind9 {
    public static void main(String [] args) {
        int[] data = {12, -3, 9, -5, 10};
        final int valueToFind = 9;

        boolean found = false;
        int count = 0;
        while ((!found) && (count < data.length)) {
            if (valueToFind == data[count]) {
                found = true;
            }
            count++;
        }

        if (found) {
            System.out.print("Found ");
        } else {
            System.out.print("Did not find ");
        }
        System.out.println(valueToFind + " in "
            + count + " comparisons");
    }
}
  • Would it be any faster to start at the end of an array?
  • If an array is sorted, then we can program faster methods -- binary search

^ top

4.1.4: Sorting an Array

  • Sorting is a common task for computers, for example:
    • Sort numbers in ascending order
    • Sort numbers in descending order
    • Sort strings in alphabetic order
  • Many different algorithms for sorting, including:
    • Bubble sort - move item up until in right place
    • Insertion sort - add elements to list one at a time
    • Selection sort - pick 1st, then 2nd, etc.
    • Quick sort - divide and conquer

Selection Sort

  • Selection sort is one of the easiest -- but not the most efficient
  • General algorithm:
    1. Find the smallest element
    2. Swap with the first element
    3. Find the smallest element in the rest of the list
    4. Swap with the first element of the rest of the list
    5. Repeat until the list is sorted

    Pass a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    Original 10 7 29 14 -4 -12 21
    First -12 7 29 14 -4 10 21
    Second -12 -4 29 14 7 10 21
    Third -12 -4 7 14 29 10 21
    Fourth -12 -4 7 10 29 14 21
    Fifth -12 -4 7 10 14 29 21
    Sixth -12 -4 7 10 14 21 29

  • How many passes were needed for a seven element array?

Selection Sort Code

  • Following is selection sort code
  • Have added some statements to show action for each pass
public class SelectionSort {
    public static void main(String [] args) {
        int[] a = {10, 7, 29, 14, -4, -12, 21};

        System.out.print("Original array: ");
        showArray(a);
        sort(a);
        System.out.print("\nSorted array: ");
        showArray(a);
    }

    public static void showArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }
        System.out.println();
    }

    public static void sort(int[] a) {
        int index, indexOfMin;
        for (index = 0; index < a.length - 1; index++) {
            indexOfMin = findMin(a, index, a.length - 1);
            swap(a, index, indexOfMin);
            System.out.print("Pass#" + index + ": ");
            showArray(a);
        }
    }

    private static int findMin(int[] a, int start, int end) {
        int indexOfMin = start;
        for (int i = start + 1; i <= end; i++) {
            if (a[i] < a[indexOfMin]) {
                indexOfMin = i;
            }
        }
        return indexOfMin;
    }

    private static void swap(int[] a, int first, int second) {
        System.out.println("\nSwapping " + a[first]
            + " with " + a[second]);
        int temp = a[first];
        a[first] = a[second];
        a[second] = temp;
    }
}
  • Note that every element in the array must have a value
  • Can the array have duplicate items?
  • Also note that the larger task was broken into smaller tasks using methods
    • Helps to organize program and improve clarity

What About Bubble Sort?

  • Another sorting algorithm that is easy to understand and use
  • General algorithm:
    1. Make array.length passes through the array
    2. For each pass, compare each array element with the next element
    3. If the current element is larger than the next one, swap them
  • Not an efficient sorting algorithm
  • Sometimes simple algorithms perform poorly
  • Simple algorithms still useful because: easy to program and understand
  • If better performance is needed, can replace with a better algorithm
  • More information: Sorting Algorithms
    • Includes Java source code
    • Not acceptable to copy bubble sort code for an assignment

^ top

4.1.5: Binary Search

  • Once an array is sorted, can use binary search to find an item
  • Binary search is much faster than sequential search
    • public class BinarySearch {
    public static void main(String [] args) {
        int[] a = {-12, -4, 7, 10, 14, 21, 29};

        int key = 14;
        System.out.print("Searching array: ");
        showArray(a);
        int index = binarySearch(a, key);
        System.out.println("Index of " + key
            + " = "+ index);
    }

    public static void showArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }
        System.out.println();
    }

    // find the index of key in array a
    // return -1 if key is not found
    public static int binarySearch(int[] a, int key) {
        int count = 0;
        int low = 0;
        int high = a.length - 1;
        int middle;
        while (low <= high) {
            count++;
            middle = (low + high) / 2;
            System.out.println("Pass#" + count
                    + " low=" + low
                    + " high=" + high
                    + " middle=" + middle);
            if (a[middle] == key) {
                return middle; // just right
            } else if (a[middle] < key) {
                low = middle + 1; // too small
            } else {
                high = middle - 1; // too big
            }
        }
        return -1;
    }
}

How Much Faster is Binary Search?

  • Given the sorted array:

    • a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    -12 -4 7 10 14 21 29

  • How many steps to find the value of 14 using sequential search?
  • How many steps to find the value of 14 using binary search?
  • On average for an array of n elements:
    • Sequential search takes n / 2 steps
    • Binary search takes log2(n) steps
  • Translating to some array sizes:

    • Array Size log2(n)
    1 0
    10 3.2
    100 6.4
    1000 9.96

  • Binary search quickly becomes worth the effort of its implementation
  • Note: binary search is one algorithm a professional should know!

^ top

4.1.6: Summary

  • A "partially filled array" is one in which values are stored in an initial segment of the array
  • Arrays work well with loops to sum data and calculate other statistics
  • Can search arrays sequentially to find a value
  • Sorting algorithms can sort an array into ascending or descending order
  • If an array is sorted, can use binary search to speed the search process

^ top

Exercise 4.1

Take one minute to prepare an answer the following question:

  1. What would be the contents of the following array after each pass of SelectionSort?
    2. int[] array = {9, 21, -7, 2, 87, -19, 47}

^ top

4.2: Multidimensional Arrays

Objectives

At the end of the lesson the student will be able to:

  • Use two-dimensional (2D) arrays
  • Apply the techniques of 2D arrays to higher dimensions
  • Arrays in Java are objects
  • Array elements can be objects, such as Strings
  • Thus, array elements can reference other arrays
  • This allows Java to have arrays of multiple dimensions (multi-D)
    • String[] one;
double[][] two;
char[][][] three;
  • Each added dimension requires one more pair of square braces
  • Will focus on two-dimensional (2D) arrays in this section
  • Just use similar techniques for multi-D arrays

Rows and Columns

  • Two-dimensional (2D) array is like a spreadsheet or table
    • First dimension is the row
    • Second dimension is the column
    • Cell is the intersection of a row and column
    • Array element corresponds to a cell in the spreadsheet
  • For the array named data:

    • data[0][0] data[0][1] data[0][2]
    data[1][0] data[1][1] data[1][2]

^ top

4.2.1: Declaring and Allocating 2D Arrays

  • To declare as a 2D int-array:
    • int[][] data;

    or

    int data[][];

    or even

    int[] data[];
  • Can allocate 2D arrays dynamically
    • int data[][];
data = new int[2][3];

    or

    int[][] data = new int[2][];
data[0] = new int[3];
data[1] = new int[3];

^ top

4.2.2: Initializing 2D Arrays

  • Like one-dimensional arrays, 2D array elements assigned default values:
    • Integer (byte, short, int, long): 0
    • Floating-point (float, double): 0.0
    • Character (char): '\u0000'
    • Boolean: false
    • Objects: null
  • Can initialize 2D arrays with static initializers or loops
  • For example: 2 row by 3 column array using static initializers:
    • int[][] data = {{1,2,3}, {4,5,6}};
  • Can process multi-D arrays by nesting loops
  • Each loop has its own counter that corresponds to an index
    • class TwoD {
   public static void main(String[] args) {
      int[][] data = {{1, 2, 3}, {2, 4, 6}};
      for (int i = 0; i < data.length; i++) {
         System.out.print("Row " + i + ": ");
         for (int j = 0; j < data[i].length; j++) {
            System.out.print(data[i][j] + ", ");
         }
         System.out.println();
      }
   }
}
  • Produces the output:
    • Row 0: 1, 2, 3,
Row 1: 2, 4, 6,

^ top

4.2.1: Example: Creating a Table

  • Methods may have multi-D array parameters
  • Methods may return a multi-D array as the value returned
  • Similar to 1D arrays, but with more brackets
  • Example: 2D int array of the multiplication table
public class MultTable {
    public static void main(String[] args) {
        int[][] table = makeTable(9);
        showTable(table);
    }

    private static int[][] makeTable(int size) {
        int[][] table = new int[size][size];
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                table[i][j] = (i + 1) * (j + 1);
            }
        }
        return table;
    }

    private static void showTable(int[][] table) {
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] < 10) {
                    System.out.print(" ");
                }
                System.out.print(table[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Notes on the Code

    private static int[][] makeTable(int size) {
  • Method makeTable returns a 2D table
    • private static void showTable(int[][] table) {
  • Method showTable takes a 2D int array as a parameter

^ top

4.2.4: Ragged Arrays

  • Ragged arrays have rows of unequal length
  • Rows can have arrays assigned of different lengths
  • Produces rows with different numbers of columns
  • For example:
    • int data[][];
data = new int[2][];  // allocate rows
data[0] = new int[5]; // allocate row 0
data[1] = new int[3]; // allocate row 1
  • Can also use static initialization
    • int[][] data = {{1,2,3,4,5}, {6,7,8}};

^ top

4.2.5: Summary

  • Arrays can have more than one index
  • Each index is called a dimension
  • Thus, multidimensional arrays have multiple indexes,
  • For example, an array with two indexes is a two-dimensional array.
  • 2D array can be thought of as a grid or table with rows and columns:
  • One index is for the row, the other for the column.
  • Multi-dimensional arrays in Java are implemented as arrays of arrays,
  • 2D array is a 1D array of 1D arrays.

^ top

Exercise 4.2

Take one minute to prepare an answer the following question:

  1. Which one of the following 2D array declarations and initializations are not valid?
    1. int[] a[] = {{1, 2}, {1}, {}, {1, 2, 3, 4}};
    2. int b[] = new int[2] {1, 2};
    3. int[] c = new int[] {1, 0, 2, 3};
    4. int d[] = new int[] {1, 2};
    5. int e[][] = {{1,2}, new int[2]};

^ top

4.3: Recursion

Objectives

At the end of the lesson the student will be able to:

  • Use recursive algorithms to solve problems
  • Implement recursive solutions in Java

"To understand recursion, one must first understand recursion."
-- Unknown

^ top

4.3.1: About Recursion

Recursion: the process of defining something in terms of itself.

Recursive Thinking

  • Recursion is a natural approach to some problems
  • Can break down a problem into one or more subproblems
  • Each subproblem is similar in form to the original problem
    • Sounds circular, but in practice is not
  • For example:
    • If we had a list of numbers
    • We had all the numbers added to a sumSoFar but the last one
    • Adding the last one to the sumSoFar would provide the answer
  • Recursion divides the problem into two parts:
    • Base case
    • Simpler problem
  • Simpler problem divides the problem again until solvable with base case
  • Must eventually terminate with the base case

Recursive Methods

  • Recursive methods implement recursive algorithms
  • Methods call themselves either directly or indirectly through another method
  • General form of recursive methods:
    • returnValue recursiveMethod(arguments) {
    if (stopping condition) { // base case
        /* do whatever at the end */;
    } else {
        //execute recursive step
        recursiveMethod(arguments);
    }
}
  • Recursive methods must eventually terminate
  • Must have at least one base, or stopping, case.

    • A base case does not execute a recursive call.

  • Base case used to stop the recursion
  • Each successive call to a method must be a "smaller version of itself" so that a base case is reached eventually.

^ top

4.3.2: Factorial: Classic Recursion

  • Recall that factorial, which is written n!, has the following definition:

    • When n = 0

    n! = 1

    And for values of n greater than 0:

    n! = n * (n-1) * (n-2) * (n-3) * ... * 1

  • Can use this definition to write a Java method that implements factorial
    • class Factorial4 {
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

    static long factorial(int n) {
        if (n <= 1)
            return 1;
        else
            return (n * factorial(n - 1));
    }
}
  • Notice that method factorial is recursive because it contains a call to itself

    • Factorial: x = factorial(4);

    main() calls factorial(4)
    factorial(4) calls factorial(3)
        factorial(3) calls factorial(2)
            factorial(2) calls factorial(1)
                factorial(1) returns 1
            factorial(2) returns 2
        factorial(3) returns 6
    factorial(4) returns 24
main() continues and assigns 24 to x

^ top

4.3.3: Writing Recursive Methods

  • To use recursion to solve a problem, you must break the problem down into subparts
  • At least one of the subparts must be similar in form to the original problem
  • As an example, let us write a method to count the number of 9's in an int array
  • Often helpful to write the header of a method to use
    • Ensures we know what the method does and how it is called
  • For instance, one possible method header is:
    • int count9s(int[] array, int n)
  • Where array is the array to search and n is the current array element we are examining
  • Now we must find a way to break the problem down into subproblems that are like the original
  • One such breakdown of the problem is:
    1. Count the number of times that 9 appears in the first n-1 elements
    2. Count whether the n-th element is the number 9
    3. Add these two numbers and return the result
  • First part of the breakdown suggests a recursive call of:
    • count9s(array, n - 1)
  • If successful, this call will return the results of the first n - 1 method calls
  • Now we must determine how we will use the results
  • If the current array element is a 9, then we want to add 1 to our results
  • Otherwise, we want to return only the count so far
  • Converting this idea to code:
    • if (array[n] == 9)
    return 1 + count9s(array, n - 1);
return count9s(array, n - 1);
  • Now must consider cases where this code will not work
  • Will not work when n < 0 because arrays cannot have negative indexes
  • This tells us to add a base case to terminate our recursion
    • if (n <= 0)
    return 0;
  • Putting all the code together, with some test code, we have:
    • public class NineCounter {
    public static void main(String[] args) {
        int[] a = {9,1,9,2,9,3,4,9,5,6,9};
        int n = count9s(a, a.length - 1);
        System.out.println("Number of 9s = " + n);
    }

    static int count9s(int[] array, int n) {
        if (n < 0) {
            return 0;
        } else if (array[n] == 9) {
            return 1 + count9s(array, n - 1);
        }
        return count9s(array, n - 1);
    }
}

^ top

4.3.4: Recursion Versus Iteration

  • All recursive algorithms or methods can be rewritten without recursion
  • Methods rewritten without recursion usually have loops, so they are called iterative methods

Iteration

  • Uses repetition structures (for, while or do-while)
  • Repetition through explicit use of repetition structure
  • Terminates when loop-continuation condition fails
  • Controls repetition by using a counter

Recursion

  • Uses selection structures (if, if-else or switch)
  • Repetition through repeated method calls
  • Terminates when base case is satisfied
  • Controls repetition by dividing problems into simpler ones

Recursion vs Iteration

  • Recursion has more overhead than iteration
  • Recursion more memory intensive than iteration
  • Recursion often can be implemented with only a few lines of code
  • Iterative methods generally run faster and use less memory space

    • When should you use recursion?

  • When efficiency is not important and it makes the code easier to understand

^ top

4.3.5: Iteration to Recursion

  • Common to convert recursive methods to iterative structures
    • Often improves performance
  • Can also convert any iterative structures to recursive methods
  • Not often useful in practice, but a good way to learn about recursion
  • As an example, will convert our array summing program to use recursion
    • public class ArraySum{
    public static void main(String [] args) {
        int[] data = {1, 2, 3, 4, 5};
        int sum = 0;
        for (int i = 0; i < data.length; i++) {
            sum = sum + data[i];
            System.out.print(data[i] + ", ");
        }
        System.out.println("\nsum = " + sum);
    }
}
  • General steps are:
    1. Determine what variables the loop uses
    2. Write a recursive method header with one parameter for each variable
    3. Use the condition that causes the termination of the iterative loop as the base case
    4. Develop expressions representing how each variable changes from one iteration a the next and make the recursive call using these expressions
    5. Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments
  • Lets follow these steps with our example

Determine the Variables the Loop Uses

  • Within the loop we see three variables used:
    • i: counter
    • data: array we are summing
    • sum: accumulator

Write the Method Header

  • Parameter list must include each of our identified variables
  • Need to specify a return type for returning the result of our recursion
  • One possible method header is:
    • int sum(int[] data, int sum, int i)

Write the Base Case

  • Use the condition that causes the termination of the iterative loop as the base case test
  • May need to reverse the condition to get the correct test
    • if (i >= data.length)
  return sum;

Write the Recursive Call

  • Determine how each variable changes from one iteration to the next
  • Develop expressions that represent the changes
  • Use the expressions in the recursive call
  • In our case, we see two changes for each iteration:
    • sum = sum + data[i];
i++;
  • We can use these two statements directly before our recursive call
    • sum = sum + data[i];
i++;
return sum(data, sum, i);
  • Can also convert the statements to expressions and make our recursive call
    • return sum(data, sum + data[i], ++i);
  • Why did we change to prefix increment operator for i?
  • Putting the entire method together, we have:
    • int sum(int[] data, int sum, int i) {
  if (i > data.length)
    return sum;
  else
    return sum(data, sum + data[i], ++i);
}
  • Note that the else is not really required

Call the Recursive Method

  • Replace the original iterative loop with a call to the recursive method
  • Use the initial value of each of the variables as arguments
  • For our example, need to call the recursive method with three values
    • int sum = sum(data, 0, 0);
  • Two of the arguments are constant values
  • Common for recursive practitioners to hide the details using another function call
    • int sum(int[] data) {
  return sum(data, 0, 0);
}

All Together Now

  • Converting our original program into a recursive program:
    • class ArraySumRec{
    public static void main(String [] args) {
        int[] data = {1, 2, 3, 4, 5};
        System.out.println("\nsum= " + sum(data));
    }

    static int sum(int[] data) {
        return sum(data, 0, 0);
    }

    static int sum(int[] data, int sum, int i) {
        if (i >= data.length) {
            return sum;
        }
        System.out.print(data[i] + ", ");
        return sum(data, sum + data[i], ++i);
    }
}

^ top

Exercise 4.3

Take two minutes to convert the following iterative code to recursive code:

public class ArrayMin {
    public static void main(String [] args) {
        int[] data = {1, 7, -1, 4, -2};
        int min = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] < min) {
                min = data[i];
            }
        }
        System.out.println("min = " + min);
    }
}

Five-Step Procedure

  1. Determine what variables the loop uses
  2. Write a recursive method header with one parameter for each variable
  3. Use the condition that causes the termination of the iterative loop as the base case
  4. Develop expressions representing how each variable changes from one iteration a the next and make the recursive call using these expressions
  5. Replace the original iterative loop with a call to the recursive method, using the initial value of each of the variables as arguments

One possible answer

^ top

Wrap Up

^ top

Home | WebCT | Announcements | Schedule | Expectations | Syllabus
Help | FAQ's | HowTo's | Links

Last Updated: September 25 2003 @18:54:26