-1
$\begingroup$

CLRS Problem : 7.4

How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ?

Original quicksort


enter image description here

Tail recursive quicksort


enter image description here

Question

Modify the code for TAIL-RECURSIVE-QUICKSORT so that the worst-case stack depth is O(n log n). Maintain the O(n log n) expected running time of the algorithm.

Answer

We are always doing a tail-recursive call on the second partition. We can modify the algorithm to do the tail recursion on the larger partition. That way, we'll consume less stack.

Both algorithms sort the both partitions. But how does the stack consume less space by operating Tail-Recursive-QuickSort on larger partition?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Jul 20 '16 at 11:36
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 20 '16 at 11:36
  • 1
    $\begingroup$ I don't understand what your question is. Is that your answer or someone else's? What have you tried towards the analysis, and where did you get stuck? (Do you have a typo in the question? Vanilla Quicksort already has $O(n)$ worst-case stack depth; what we want is $O(\log n)$.) $\endgroup$ – Raphael Jul 20 '16 at 11:37
  • $\begingroup$ So, why the expected depth is $O(\log N)$ if we choose a pivot randomly every call? $\endgroup$ – Mr. Newman Oct 7 '17 at 17:23
1
$\begingroup$

Quicksort may split an array of size n into two arrays of size (n-1) and 1 if you are unlucky. So a recursive call might be given an array of size (n-1) and make a recursive call with an array of size (n-2) and so on, for a maximum recursion depth of n.

Note that one of the array parts must have a size ≤ n/2. So which one do you sort by starting at the beginning of the loop, and which one do you sort by recursion?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.