The Quicksort algorithm of Section 7.1 contains two recursive calls to itself. A

Question

The Quicksort algorithm of Section 7.1 contains two recursive calls to itself. After Quicksort calls Partition, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in 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: TAIL-Recursive-Quicksort(A, p, r) 1 while p

Explanation / Answer

Tail recursion is useed to optmise recursion calls, by using complier stack frame for further recursive
calls. So instead of hundreds of stack frames by normal recursion, we can use this tail recursion
so that it works fast, and dont require extra any stack frames. This is possible because compiler
knows that when tail recursion calls, there is no need to have extra stack frames and also copying
earlier variables data. Simply it reuses the stack frame.

Coming to given algorithm Tail-Recursive-Quicksort(A,p,r) works fine.
In algorithm..
q = PARTITION(A,p,r)
recursively sorts only left sub array... it sorts many left array parts so that until the array
has only one elment left to sort. So that it makes function less recursive. It works fine and it sorts good.
So that it has complexity of O(log2(n))

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.