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

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

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 }

`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

`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

`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

**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.

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

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

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

`bigOh4`

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

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

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

`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:** 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); } }

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

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

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