question archive One can optimize Quicksort to eliminate the cost of function calls by replacing the recursion with a stack to track the sub-arrays that should be processed “recursively
Subject:Computer SciencePrice: Bought3
One can optimize Quicksort to eliminate the cost of function calls by replacing the recursion with a stack to track the sub-arrays that should be processed “recursively.”
(a) How many sub-arrays can be put on the stack in the worst case?
(b) Quicksort makes two recursive calls. The algorithm could be changed to make these two calls in a specific order. In what order should the two calls be made so as to minimize the size needed for the stack, and how does this affect how large the stack can become?