n each of the following questions, you are given an input array A with n elements, where n is a very large positive integer. You will then compare two sorting algorithms and justify which of the two algorithms is faster in sorting this array A. In your responses, you must clearly explain which of the two algorithms runs faster. Make sure you rigorously justify your answer, carefully proving whether each algorithm is O(n), O(n log n), or O(n2). (a) Let A = [n, n -1, n - 2, . . . . 3, 2, 1] be an array where the rst n positive integers are listed in decreasing order. Determine whether Heapsort or Quicksort sorts this array faster. For this question, assume the Quicksort pivot is always the right-most element. (b) Let A be an array, where each of the n elements is a randomly chosen digit between 0 and 9. For example, if n = 12, this array could be A = [3, 5, 1, 0, 5, 7, 9, 2, 2, 8, 8, 6]. Determine whether Counting Sort or Merge Sort sorts this array faster.
In each of the following questions, you are given an input array A with n elements, where n is a very large
positive integer. You will then compare two sorting algorithms and justify which of the two algorithms
is faster in sorting this array A.
In your responses, you must clearly explain which of the two algorithms runs faster. Make sure you
rigorously justify your answer, carefully proving whether each
(a) Let A = [n, n -1, n - 2, . . . . 3, 2, 1] be an array where the rst n positive integers are listed in
decreasing order.
Determine whether Heapsort or Quicksort sorts this array faster.
For this question, assume the Quicksort pivot is always the right-most element.
(b) Let A be an array, where each of the n elements is a randomly chosen digit between 0 and 9.
For example, if n = 12, this array could be A = [3, 5, 1, 0, 5, 7, 9, 2, 2, 8, 8, 6].
Determine whether Counting Sort or Merge Sort sorts this array faster.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps