QuickSort Evaluation of Recursion Depth

Question

Being the recursion depth of the maximum number of consecutive recursive calls, before QuickSort gets the wink of the base case, and noting that it (the recursion depth) is a random variable because it depends on the selected axis.

I want to evaluate the minimum possible and maximum possible depth of QuickSort recursion.

The following procedure describes how QuickSort typically runs:

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 

A second recursive call in QuickSort is not needed; it can be avoided by using an iterative control structure. This method is also called tail recursion, and can be implemented as follows:

 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, information for the most recent call is at the top of the stack, and information for the initial call is at the bottom. When a procedure is called, its information is pushed onto the stack; when it completes, its information pops up. Since I assume that the parameters of the array 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 & theta; (n).

So, after all this, how can I evaluate the minimum possible and maximum possible recursion depth of each version of QuickSort? Am I correct in the above conclusion?

Thanks in advance.

Answer 1

Worst case

The worst behavior for quicksort occurs when the split routine creates one subtask with elements n -1 and one with 0 elements. Partitioning Costs & theta; (n) time. If the partition is maximally unbalanced at each recursive level of the algorithm, then the depth of the tree is n, and the worst case is the worst behavior for quicksort & theta; (n ^ 2), as you see the last level number of the corresponding recursion tree in the worst case is & theta; (n).

Best case

In the most possible split, PARTITION creates two subtasks, each of which has a size of no more than n = 2, since one has a floor size (n / 2) and one of the floor (n / 2) -1. In this case, quicksort is much faster. The recursion tree in this case is what is known as a complete binary tree. It can have from 1 to 2 nodes, as far as possible, at the last level h, then h = log n, then the best behavior for quicksort & theta; (nlog n), and, as you can see, the last level number of the corresponding recursion tree is at best & theta; (log n).

Conclusion

Minimum: & theta; (log (n))

Maximum: & theta; (n)

Answer 2

It depends a lot on how you code the algorithm. Usually a smaller part is performed using a recursive call, a large part is iterated within the same embodiment. With this approach, the maximum depth is log2 (N), the minimum depth is 1.

At each step, the smaller part can be no more than half of the range. So in the worst case, you need the steps log2 (N) to reach size 1.

The other extreme is that the smaller part always has a size of only one. In this case, recursive calls are not required.