## Exercise 3: Sorting, Searching, and Big O

**Written Exercises**

**A3Q1**

Suppose an array called scores contains the elements 23, 27, 30, 34, 41, 51, 55, 57, 60, 67, 72, 78, 83, 96

In an organized manner, trace the execution of Sequential Search and Binary Search Algorithms to search for the number 41

**A3Q2**

Trace through the execution of Bubble Sort as it sorts through the following array in ascending order: 25 30 20 80 40 60

**A3Q3**

What is the maximum number of comparisons that might be required to perform a binary search on a list containing seven items? Explain the situation and include an example of such a list and search.

**A3Q4**

For large arrays, in the worst case, is selection sort faster than insertion sort? Explain.

**A3Q5**

What is the best Big O value that any search algorithm can be? Explain.

**Programming Exercises**

**A3Q6**

Rewrite insertion sort so that it arranges values of an array in descending order

**A3Q7**

Another way to sort a large array that contains numbers from 0 to 100 is to use an array of size 101 (the spots 0 to 100). We will call this smaller array the tracker array. To sort the list, we cycle through the large array and keep track of how many times we see a specific number using the tracker array. This sorting algorithm is known as Counting Sort. Write the Java method for Counting Sort that will take an array as a parameter and sort it using this method of sorting. We will assume that only the numbers from 0 to 100 will be in the array. Determine the order of Counting Sort. Why is this algorithm not as useful as a general sorting algorithm?

**A3Q8**

Write a version of insertion sort that will take in an array of Strings and place the in Alphabetical Order.

**Hint:**By using the compareTo(str) command in Java. It will return 0, a positive number, or a negative number depending on what order they should be in.