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:

• practice linear (sequential) search and binary search
• gain familiarity with algorithmic complexity classes and big-Oh
• practice selection sort and merge sort
• learn how to search and sort both primitives and objects

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

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.

• 7, 11, 9

What value would be returned from the binary search?

• 9

Exercise : binarySearch2

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.

• 6, 2, 4, 3

What value would be returned from the binary search?

• -4

Exercise : binarySearch3

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.

• 6, 9, 7, 8

What value would be returned from the binary search?

• -9

Algorithmic Complexity and Big-Oh

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

• Any single statement takes the same amount of time to run.
• A method call's runtime is measured by the total of the statements inside the method's body.
• A loop's runtime, if the loop repeats N times, is N times the runtime of the statements in its body.

Big-Oh: Notation for describing algorithmic complexity classes.

• Estimate the highest power of N, then throw away constants and lower powers of N.
• Example, if an algorithm runs approximately (0.5N^2 + 15N + 78) statements, we say it runs "on the order of" N^2, or O(N^2) for short.

Exercise -a: bigOh

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

• O(log N)

Exercise -b: 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;
}

• O(1)

Exercise -c: 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();
}

• O(N)

Exercise -d: 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--;
}

• O(N^2)

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

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);

• after pass 1: {12, 29, 19, 48, 23, 55, 74, 37}
• after pass 2: {12, 19, 29, 48, 23, 55, 74, 37}
• after pass 3: {12, 19, 23, 48, 29, 55, 74, 37}

Exercise : selectionSort2

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);

• after pass 1: {-9, 5, 8, 14, 0, -1, -7, 3}
• after pass 2: {-9, -7, 8, 14, 0, -1, 5, 3}
• after pass 3: {-9, -7, -1, 14, 0, 8, 5, 3}

Exercise : selectionSort3

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);

• after pass 1: {9, 63, 45, 72, 27, 18, 54, 36}
• after pass 2: {9, 18, 45, 72, 27, 63, 54, 36}
• after pass 3: {9, 18, 27, 72, 45, 63, 54, 36}

Merge Sort

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

• Divide the list into two roughly equal halves.
• Sort the left half; Sort the right half.
• Merge the two sorted halves into one sorted list.

// 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

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);

• 1st split: {63, 9, 45, 72} {27, 18, 54, 36}
• 2nd split: {63, 9} {45, 72} {27, 18} {54, 36}
• 3rd split: {63} {9} {45} {72} {27} {18} {54} {36}
• 1st merge: {9, 63} {45, 72} {18, 27} {36, 54}
• 2nd merge: {9, 45, 63, 72} {18, 27, 36, 54}
• 3rd merge: {9, 18, 27, 36, 45, 54, 63, 72}

Exercise : mergeSort2

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);

• 1st split: {15, 56, 24, 5} {39, -4, 27, 10}
• 2nd split: {15, 56} {24, 5} {39, -4} {27, 10}
• 3rd split: {15} {56} {24} {5} {39} {-4} {27} {10}
• 1st merge: {15, 56} {5, 24} {-4, 39} {10, 27}
• 2nd merge: {5, 15, 24, 56} {-4, 10, 27, 39}
• 3rd merge: {-4, 5, 10, 15, 24, 27, 39, 56}

Exercise : mergeSort3

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);

• 1st split: {22, 88, 44, 33} {77, 66, 11, 55}
• 2nd split: {22, 88} {44, 33} {77, 66} {11, 55}
• 3rd split: {22} {88} {44} {33} {77} {66} {11} {55}
• 1st merge: {22, 88} {33, 44} {66, 77} {11, 55}
• 2nd merge: {22, 33, 44, 88} {11, 55, 66, 77}
• 3rd merge: {11, 22, 33, 44, 55, 66, 77, 88}