# The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After the call to PARTITION,

## Question:

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.

Fantastic news! We've Found the answer you've been seeking!

## Step by Step Answer:

**Related Book For**

## Discrete Mathematics and Its Applications

**ISBN:** 978-0073383095

7th edition

**Authors:** Kenneth H. Rosen