7-4 Stack depth for quicksort

The \(\text{QUICKSORT}\) algorithm of Section 7.1 contains two recursive calls to itself. After \(\text{QUICKSORT}\) calls \(\text{PARTITION}\), it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in \(\text{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:

C++
1
2
3
4
5
6
TAIL-RECURSIVE-QUICKSORT(A, p, r)
    while p < r
        // Partition and sort left subarray.
        q = PARTITION(A, p, r)
        TAIL-RECURSIVE-QUICKSORT(A, p, q - 1)
        p = q + 1

a. Argue that \(\text{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 \(\text{TAIL-RECURSIVE-QUICKSORT}\)'s stack depth is \(\Theta(n)\) on an \(n\)-element input array.

c. Modify the code for \(\text{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. The book proved that \(\text{QUICKSORT}\) correctly sorts the array \(A\). \(\text{TAIL-RECURSIVE-QUICKSORT}\) differs from \(\text{QUICKSORT}\) in only the last line of the loop.

It is clear that the conditions starting the second iteration of the while loop in \(\text{TAIL-RECURSIVE-QUICKSORT}\) are identical to the conditions starting the second recursive call in \(\text{QUICKSORT}\). Therefore, \(\text{TAIL-RECURSIVE-QUICKSORT}\) effectively performs the sort in the same manner as \(\text{QUICKSORT}\). Therefore, \(\text{TAIL-RECURSIVE-QUICKSORT}\) must correctly sort the array \(A\).

b. The stack depth will be \(\Theta(n)\) if the input array is already sorted. The right subarray will always have size \(0\) so there will be \(n − 1\) recursive calls before the while-condition \(p < r\) is violated.

c.

C++
1
2
3
4
5
6
7
8
9
MODIFIED-TAIL-RECURSIVE-QUICKSORT(A, p, r)
    while p < r
        q = PARTITION(A, p, r)
        if q < floor((p + r) / 2)
            MODIFIED-TAIL-RECURSIVE-QUICKSORT(A, p, q - 1)
            p = q + 1
        else
            MODIFIED-TAIL-RECURSIVE-QUICKSORT(A, q + 1, r)
            r = q - 1
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用