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

}
```

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