Status: Tags: Links: [[
CMPT 125 Searching and Sorting Practice Problems
Searching and Sorting
Problems
- How many comparisons and will Binary Search make on input A = [1,2,3,4,5,6,7] when searching for 5? ?
- Compare 5 to 4, go to [5,6,7]
- Compare 5 to 6, go to [5]
- Compare 5 to 5, found elem
- How many comparisons and how many swaps will SelectionSort perform on the array A = [3, 5, 1, 8, 4]? Explain your answer. Write some intermediate steps of the algorithm when necessary.
?
- Compare 3,5 3,1 1,8 1,4 1 swap (3,1), A = 15384
- Compare 5,3 3,8 3,4 1 swap (3,5), A = 13584
- Compare 5,9 5,4 1 swap (5,4), A = 13485
- Compare 8,5 1 stap (8,5), A = 13458
- 10 comparisons, 4 swaps
- How many swaps will InsertionSort perform on the array A = [3, 5, 1, 8, 4]? Explain your answer. Write some intermediate steps of the algorithm when necessary.
?
- Start at 5, no swap
- Start at 1, swap (5,1), swap (3,1), two swap
-
Consider the Quicksort algorithm that chooses as a pivot the first element of the array. How many swaps will it perform on the array A = [6,1,2,3,4,5]? Explain your answer. Write some intermediate steps of the algorithm when necessary.
-
Consider the Quicksort algorithm that chooses as a pivot the last element of the array. How many swaps will it perform on the array A = [6,1,2,3,4,5]? Explain your answer. Write some intermediate steps of the algorithm when necessary.
-
Consider the MergeSort algorithm (with linear time merging we saw in class). How many comparisons will it perform on the array A = [5,4,3,2,1,4,7,8]? Explain your answer. Write some intermediate steps of the algorithm when necessary.
-
Give an example of an array of length n on which InsertionSort makes exactly 1 swap in each iteration of the outer loop.
-
Give an example of an array of length 6 on which InsertionSort makes a total of 15 swaps.
-
Prove that on any array of length 6 InsertionSort makes at most 15 swaps.
-
What is the running time of InsertionSort on a sorted array?
Backlinks
|
|
References:
Created:: 2021-10-24 12:10