# Question

The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After the call to PARTITION, the left subarray is recursively sorted and then the right subarray is recursively sorted. The second recursive call in QUICKSORT is not really necessary; it can be avoided by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quick sort, which simulates tail recursion.

QUICKSORT'(A, p, r)

1 while p < r

2 do ▸ Partition and sort left subarray.

3 q ← PARTITION (A, p, r)

4 QUICKSORT'(A, p, q - 1)

5 p ← q + 1

a. Argue that QUICKSORT'(A, 1, length[A]) correctly sorts the array A. Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O (1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

b. Describe a scenario in which the stack depth of QUICKSORT' is Θ (n) on an n-element input array.

c. Modify the code for QUICKSORT' so that the worst-case stack depth is Θ (lg n). Maintain the O (n lg n) expected running time of the algorithm.

QUICKSORT'(A, p, r)

1 while p < r

2 do ▸ Partition and sort left subarray.

3 q ← PARTITION (A, p, r)

4 QUICKSORT'(A, p, q - 1)

5 p ← q + 1

a. Argue that QUICKSORT'(A, 1, length[A]) correctly sorts the array A. Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O (1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.

b. Describe a scenario in which the stack depth of QUICKSORT' is Θ (n) on an n-element input array.

c. Modify the code for QUICKSORT' so that the worst-case stack depth is Θ (lg n). Maintain the O (n lg n) expected running time of the algorithm.

## Answer to relevant Questions

a. Suppose that each leaf of TA is labeled with the probability that it is reached given a random input. Prove that exactly n! Leaves are labeled 1/n! And that the rest are labeled 0.b. Let D(T) denote the external path ...The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small ...The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7- point problem. The general problem ...In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to ...Show how to solve the fractional knapsack problem in O (n) time. Assume that you have a solution to Problem 9-2.Post your question

0