Building Java Programs

Lab: Searching and Sorting

Except where otherwise noted, the contents of this document are Copyright 2019 Stuart Reges and Marty Stepp.

Lab goals

Goals for this problem set:

Recall: binary search algorithm

Binary search successively eliminates half the data from consideration. Here is the algorithm we will be discussing in the following exercises:

// Returns the index of an occurrence of target in a,
// or a negative number "insertion point" if target is not found.
// Precondition: elements of a are in sorted order
public static int binarySearch(int[] a, int target) {
    int min = 0;
    int max = a.length - 1;

    while (min <= max) {
        int mid = (min + max) / 2;
        if (a[mid] < target) {
            min = mid + 1;
        } else if (a[mid] > target) {
            max = mid - 1;
        } else {
            return mid;   // target found
        }
    }

    return -(min + 1);    // target not found
}

Exercise : binarySearch practice-it

Suppose we are performing a binary search on a sorted array called numbers initialized as follows:

// index          0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
int[] numbers = {-1,  3,  5,  8, 15, 18, 22, 39, 40, 42, 50, 57, 71, 73, 74};

// search for the value 42
int index = binarySearch(numbers, 42);

What indexes would be examined by the binary search (the mid values in our algorithm's code)? Write them separated by commas such as 1, 2, 3.

What value would be returned from the binary search?

Exercise : binarySearch2 practice-it

Suppose we are performing a binary search on a sorted array called numbers initialized as follows:

// index          0   1   2   3   4   5   6   7   8   9  10  11  12  13
int[] numbers = {-2,  0,  1,  7,  9, 16, 19, 28, 31, 40, 52, 68, 85, 99};

// search for the value 5
int index = binarySearch(numbers, 5);

What indexes would be examined by the binary search (the mid values in our algorithm's code)? Write them separated by commas such as 1, 2, 3.

What value would be returned from the binary search?

Exercise : binarySearch3 practice-it

Suppose we are performing a binary search on a sorted array called numbers initialized as follows:

// index          0   1   2   3   4   5   6   7   8   9  10  11  12
int[] numbers = {-5, -1,  3,  5,  7, 10, 18, 29, 37, 42, 58, 63, 94};

// search for the value 33
int index = binarySearch(numbers, 33);

What indexes would be examined by the binary search (the mid values in our algorithm's code)? Write them separated by commas such as 1, 2, 3.

What value would be returned from the binary search?

Algorithmic Complexity and Big-Oh

complexity class: A category of algorithm based on its rate of growth relative to some input variable or parameter.

Big-Oh: Notation for describing algorithmic complexity classes.

Exercise : bigOh practice-it

Approximate the runtime of the following code fragment, in terms of N. Write your answer in a format such as O(N^2) or O(N log N).

int sum = 0;
int j = 1;
while (j <= N) {
    sum++;
    j = j * 2;
}

Exercise : bigOh2

Approximate the runtime of the following code fragment, in terms of N. Write your answer in a format such as O(N^2) or O(N log N).

int sum = 0;
for (int i = 1; i < 10; i++) {
	sum = sum * 5;
}

Exercise : bigOh3

Approximate the runtime of the following code fragment, in terms of N. Write your answer in a format such as O(N^2) or O(N log N).

int x = 5;
double y = 3.5;
String s = "hi";

for (int i = 1; i <= N; i++) {
    x++;
}

for (int i = 1; i <= N; i++) {
    x--;
    y++;
    x += s.length();
}

Exercise : bigOh4

Approximate the runtime of the following code fragment, in terms of N. Write your answer in a format such as O(N^2) or O(N log N).

int x = 5;

for (int i = 1; i <= N; i++) {
    for (int i = 1; i <= N / 2; i++) {
        x++;
    }
}

for (int i = 1; i <= 3 * N; i++) {
    x--;
}

Selection Sort

selection sort: Orders a list of values by repeatedly putting the smallest or largest unplaced value into its final position.

// Rearranges the elements of a into sorted order using
// the selection sort algorithm.
public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        // find index of smallest remaining value
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }

        // swap smallest value its proper place, a[i]
        if (i != min) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

Exercise : selectionSort practice-it

Write the state of the elements of the array below after each of the first 3 passes of the outermost loop of the selection sort algorithm.

// index          0   1   2   3   4   5   6   7
int[] numbers = {37, 29, 19, 48, 23, 55, 74, 12};
selectionSort(numbers);

Exercise : selectionSort2 practice-it

Write the state of the elements of the array below after each of the first 3 passes of the outermost loop of the selection sort algorithm.

// index          0   1   2   3   4   5   6   7
int[] numbers = { 8,  5, -9, 14,  0, -1, -7, 3};
selectionSort(numbers);

Exercise : selectionSort3 practice-it

Write the state of the elements of the array below after each of the first 3 passes of the outermost loop of the selection sort algorithm.

// index          0   1   2   3   4   5   6   7
int[] numbers = {63,  9, 45, 72, 27, 18, 54, 36};
selectionSort(numbers);

Merge Sort

merge sort: Repeatedly divides the data in half, sorts each half, and combines the sorted halves into a sorted whole. (usually recursive)

// Rearranges the elements of a into sorted order using
// the merge sort algorithm (recursive).
public static void mergeSort(int[] a) {
    if (a.length >= 2) {
        // split array into two halves
        int[] left  = Arrays.copyOfRange(a, 0, a.length/2);
        int[] right = Arrays.copyOfRange(a, a.length/2, a.length);

        // sort the two halves
        mergeSort(left);
        mergeSort(right);

        // merge the sorted halves into a sorted whole (code not shown)
        merge(a, left, right);
    }
}

Exercise : mergeSort practice-it

Trace the complete execution of the merge sort algorithm when called on the array below. Show the sub-arrays that are created by the algorithm and show the merging of sub-arrays into larger sorted arrays.

// index          0   1   2   3   4   5   6   7
int[] numbers = {63,  9, 45, 72, 27, 18, 54, 36};
mergeSort(numbers);

Exercise : mergeSort2 practice-it

Trace the complete execution of the merge sort algorithm when called on the array below. Show the sub-arrays that are created by the algorithm and show the merging of sub-arrays into larger sorted arrays.

// index          0   1   2   3   4   5   6   7
int[] numbers = {15, 56, 24,  5, 39, -4, 27, 10};
mergeSort(numbers);

Exercise : mergeSort3 practice-it

Trace the complete execution of the merge sort algorithm when called on the array below. Show the sub-arrays that are created by the algorithm and show the merging of sub-arrays into larger sorted arrays.

// index          0   1   2   3   4   5   6   7
int[] numbers = {22, 88, 44, 33, 77, 66, 11, 55};
mergeSort(numbers);