USA: +1 (725) 712-1730
USA: +1 (725) 712-1730

Answered! Algorithm Analysis Question:The QUICKSORT algorithm of section 7.1 contains two recursive calls to itself. After…

2. [40 Pts] Algorithm Analysis 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. 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 quicksort, which simulates tail recursion. QUICKSORT (A, p, r) While p <r 2 do D Partition and sort left subarray g PARTITION (A, p r) QUICKSORT (A, p, q-1) q 1 a. Argue that QUICKSORT (A, 1, length LAD correctly sorts 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 O (n) on an n-element input array Modify the code for QUICKSORT so that the worst case stack depth is O lg n) while maintaining the O (n lg n) expected running time of the algorithm.

Algorithm Analysis 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. 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 quicksort, which simulates tail recursion. QUICKSORT’ (A, p, r) while p

Expert Answer

 a) We should start with what is tail recursion ! In a recursive function if recursive call is the last thing executed by the function then it is tail recursive. As we can see here the function only makes one recursive call and that to sort the the left array. After recursive calling of the QUICKSORT(A,p, q -1), we enter in to the left and then it goes on and goes. Sorting the left part of each array, but how is right array sorted? the statement p–> q +1 takes care of that, as p is kept to have q+1 then next time we enter the loop the right array is sorted becasue q <– partition(A, p, r), here p has been changed to the starting index of right array and r is the ending index. Hence, both the arrays are taken case of. The benefit of this would be using the stack frame again, meaning a tail-recursive function will only use a single stack frame rather than n stack frame as by normal recursive function.

b) We managed to reduce the number of recursive calls by using tail-recursion but it can still use O(n) space in the worst case. How? If the array is sorted in decreasing order and last element is our pivot, then out left array will always have n-1 elements, making the stack go up to n. So this can be the scenario.

c) What if we just called recursion for the smaller part after the partition happens? If that is done, we can always have O(log n) as stack depth. Consider the code:
QuickSort(A, p, r)
while (p < r)
q = partition(A, p, r)
if (q – p < r – q) // if left part is smaller
quickSort(A, p, q – 1) //recursive call for left part
p = q + 1 //handle the right part
else //if right part is smaller
quickSort(A, q + 1, r) // recursive call for right part
r = q – 1 //handle the left part

This will ensure that recursion is always done on smaller part of the array i.e. reducing the size of the stack to almost half. The runtime is not affected as the same amount of work has to be done as before.

If you have any further doubts, let me know in the comments !

Still stressed from student homework?
Get quality assistance from academic writers!
Order now