Consider the following array:
40 63 64 2 87 62 45 66 99 30 31 57
Note: For quicksort you will use a different set of numbers, because these resulted in pivots being the largest or smallest item too often. For quicksort use these numbers instead:
13 72 0 43 28 86 63 50 3 29 36 40
For problems 1 - 5, create a diagram showing the state of the array above after each pass through the array using the following sorting algorithms. (In other words, use the method used in lecture to show how each sorting algorithm sorts the numbers above.) Also, for each algorithm, state the average big-O running time estimate.
For consistency, please use the algorithm as shown in the lecture, not in the text.
6. List each number from the unsorted list above (the list that starts with 40) that will be examined if a linear search is used to search for the number 62. Also state the average big-O running time estimate for a linear search.
7. Here are the same numbers but sorted:
02 30 31 40 45 57 62 63 64 66 87 99
List each number from the list above that will be examined if a binary search is used to search for the number 99.
8. List each number from the list above that will be examined if a binary search is used to search for the number 52. Note that 52 is not in the list. That doesn't change anything. There is still a sequence of numbers that are examined until the algorithm determines that it isn't there.
9. State the average big-O running time estimate for binary search.