QuickSort's estimation of recursion depth

问题:

Being the recursion depth the maximum number of successive recursive calls before QuickSort hits it´s base case, and noting that it (recursion depth) is a random variable, since it depends on the chosen pivot.

What I want is to estimate the minimum-possible and maximum-possible recursion depth of QuickSort.

The following procedure describes the way thats QuickSort is normally implemented:

QUICKSORT(A,p,r)
    if p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        QUICKSORT(A,q+1,r)
    return A

PARTITION(A,p,r)
    x←A[r]
    i←p−1
    for j ←p to r−1
        if A[j] ≤ x
            i ← i +1
            exchange A[i] ↔ A[j]
    exchange A[i +1] ↔ A[r]
    return i +1

The second recursive call in QuickSort is not really necessary; it can be avoided by using an iterative control structure. This technique is also called tail recursion, and it can be implemented like:

QUICKSORT_tail(A,p,r)
    while p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        p ← q+1
    return A

In this version, 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 I assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O(1) stack space. I also believe that the maximum-possible stack space with this version should be θ(n).

So, after all this said, how can I estimate the minimum-possible and maximum-possible recursion depth of each QuickSort version? Am I right in the above inference?

Thanks in advance.

回答1:

Worst-case

The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with n -1 elements and one with 0 elements.The partitioning costs θ(n) time. If the partitioning is maximally unbalanced at every recursive level of the algorithm, then the depth of the tree is n and the worst case is θ(n) the worst-case behavior for quicksort θ(n^2), as you see the number of the last level of the corresponding recursion tree in the worst case is θ(n).

Best-case

In the most even possible split, PARTITION produces two subproblems, each of size no more than n=2, since one is of size floor(n/2) and one of size floor(n/2) -1. In this case, quicksort runs much faster.The recursion tree in this case is what is known as complete binary tree It can have between 1 and 2h nodes, as far left as possible, at the last level h, then h = log n, then the best-case behavior for quicksort θ(nlog n), and as you see the number of the last level of the corresponding recursion tree in the best case is θ(log n).

Conclusion

Minimum: θ(log(n))

Maximum: θ(n)

回答2:

This depends very much on how you code the algorithm. Usually, just the smaller part is done with a recursive call, the larger part is done by an iteration within the same incarnation. With this approach, the maximal depth is log2(N), the minimal depth is 1.

In each step the smaller part can be at most half the size of the range. So in the worst case you need log2(N) steps to reach a size of 1.

The other extreme is when the smaller part has always only size one. In this case there are no recursive calls needed.