7-4

The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After QUICKSORT calls PARTITION, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in QUICKSORT is not really necessary; we can avoid it by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion: TAIL-RECURSIVE-QUICKSORT(A, p, r)
1 while p < r
2 // Partition and sort left subarray.
3 q = PARTITION(A, p, r)
4 TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
5 p = q + 1
a. Argue that TAIL-RECURSIVE-QUICKSORT(A, 1,A:length) 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. Upon calling a procedure, 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 TAIL-RECURSIVE-QUICKSORT’s stack depth is $\theta(n)$ on an n-element input array. c. Modify the code for TAIL-RECURSIVE-QUICKSORT so that the worst-case stack depth is $\theta(lg n)$. Maintain the O(n lg n) expected running time of the algorithm.
a. TAIL-RECURSIVE-QUICKSORT performs same operations as QUICK-SORT. Quicksort calls itself recursively with A,p,q-1 and A,q+1,r arguments. TAIL-RECURSIVE-QUICKSORT does the same calls as well. It intially recursively calls it self with A,p,q-1 later it sets p value to q+1 and using the while it calls it does same operations as calling it self with A,q+1,r arguments.
b.TAIL-RECURSIVE-QUICKSORT will have a stack of depth $\theta(n)$ when calls to PARTITION return a q value of r(q=r).This happens when we an already sorted array. Below are sequence of calls:
TAIL-RECURSIVE-QUICKSORT(A,p,n)
TAIL-RECURSIVE-QUICKSORT(A,p,n-1)
TAIL-RECURSIVE-QUICKSORT(A,p,n-2)
.
.
.
TAIL-RECURSIVE-QUICKSORT(A,p,1)
c. The TAIL-RECURSIVE-QUICKSORT can be modified as below.
TAIL-RECURSIVE-QUICKSORT(A,p,r)
q = PARTITION(A,p,r)
if q-p < r-q
TAIL-RECURSIVE-QUICKSORT'(A,p,q-1)
r = q+1
else
TAIL-RECURSIVE-QUICKSORT'(A,q+1,r)
r = q-1
TAIL-RECURSIVE-QUICKSORT'(A,p,r)
if you see in b TAIL-RECURSIVE-QUICKSORT will push more recursive call to stack if the size of the first partition is large. At a time you will $\theta(n)$ calls on the stack. we can eliminate this by using the modified procedure which calls the TAIL-RECURSIVE-QUICKSORT' for small partition. The best case scenario we will have array with equal sizes of n/2. This will occupy stake depth of $\theta(log n)$ using recursion
$$S(n) = 2 S(n/2)$$ this master theorem case 1 which $\theta(log n)$.
This will change the running time since we only changed the order of processing the algorithm hence the expected running time is $O(n log n)$.