Searching
List: 3, 8, 7, 9, 11, 13, 5, 20, 6, 10
Sequential Search
1) How many comparisons would need to be made if searching for 20?
2) How many comparisons are made by sequential search in:
a) The best case b) The worst case c) The average case
Binary Search
3) What is one disadvantage of binary search compared to sequential search?
List: 2, 8, 12, 19, 25, 33, 40, 50, 55, 63, 80,
4) Trace the “left”, “right” and “mid” when searching for:
a) 8
b) 60
4) Using the binary search, how many comparisons in the:
a) best case scenario b) worst case scenario
5) When using binary search, how many comparisons would need to be made to find a target value in a list of 5,000 elements (in the worst-case scenario)?
6) public int sequentialSearch(double[] numbers, double wanted)
7) public int binarySearch(String[] words, String target, int low, int high) //iterative i.e. loop
8) public int binarySearch(int[] ints, int target, int low, int high)//recursive
General Understanding of Sorts (Selection, Insertion, Merge)
Universal List for all Sort Problems (We are trying to sort in ascending order)
7, 3, 5, 8, 2, 6, 9, 1
9) Using Selection Sort, show what the list looks like after each pass of the outer loop.
10) How many comparisons are made to sort the list?
11) How many comparisons would have to be made if the list were already sorted in ascending order?
12) Using insertion sort, show what the list looks like after each pass of the outer loop.
13) How many comparisons were made to sort the list? Look back at how many comparisons were made to correctly “insert” the value for each pass.
14) How many comparisons would need to be made if the list were already sorted in ascending order?
14b) worst case: descending order
If we used a merge sort, first the list would be partitioned into two roughly equal lists:
15) Show the list partitions until the base case is met (like shown below).
16) State what the base case is in words.
17) Show the list partitions as the individual partitions “merge” into one list:
18) How many comparisons were made for merge sort in this example?
The efficiency of merge sort in the worst case is (or NlogN for short even though I don’t know for sure if you need to know this). This means that “usually” merge sort is faster than selection or insertion sort for large lists. However, insertion sort would be faster if the list were sorted or almost sorted (remember the best case for insertion is n-1 comparisons).
Sorts with Code
19) public void selectionSort(int[] ints)
20) public void insertionSort(double[] dubs)
21) public int[] merge(int[] a, int[] b)
precondition: Arrays ‘a’ and ‘b’ are sorted.
Postcondition: A sorted array consisting of the values from a and b is returned.