By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,771 Members | 1,763 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,771 IT Pros & Developers. It's quick & easy.

Removing Tail recursions in quicksort

P: n/a
Hey,
Here is the pseudocode of quicksort. It can be observed that there
are as many as (n-1) unresolved stack calls in the worst case. Now, how
do i reduce this unresolved stack calls? what modifications should I
make?

procedure QuickSort(L[0:n-1], low, high) recursive
Input: L[0:n-1] (a list of size n), low, high (integers)
Output: L[low:high] is sorted
if high > low then
Partition(L[0:n-1], low, high, position)
QuickSort(L[0:n-1], low, position - 1)
QuickSort(L[0:n-1], position + 1, high)
endif
end QuickSort
thanks,

Haran

Oct 19 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a

nk*****@gmail.com wrote:
Hey,
Here is the pseudocode of quicksort. It can be observed that there
are as many as (n-1) unresolved stack calls in the worst case. Now, how
do i reduce this unresolved stack calls? what modifications should I
make?

procedure QuickSort(L[0:n-1], low, high) recursive
Input: L[0:n-1] (a list of size n), low, high (integers)
Output: L[low:high] is sorted
if high > low then
Partition(L[0:n-1], low, high, position)
QuickSort(L[0:n-1], low, position - 1)
QuickSort(L[0:n-1], position + 1, high)
endif
end QuickSort


I would expect only log2(n) levels of recursion for a quicksort of n
items. So I would change the pseudocode to be a less recursive
implementation.

Greg

Oct 19 '05 #2

P: n/a
nk*****@gmail.com wrote:
Hey,
Here is the pseudocode of quicksort. It can be observed that there
are as many as (n-1) unresolved stack calls in the worst case. Now, how
do i reduce this unresolved stack calls? what modifications should I
make?

procedure QuickSort(L[0:n-1], low, high) recursive
Input: L[0:n-1] (a list of size n), low, high (integers)
Output: L[low:high] is sorted
if high > low then
Partition(L[0:n-1], low, high, position)
QuickSort(L[0:n-1], low, position - 1)
QuickSort(L[0:n-1], position + 1, high)
endif
end QuickSort
thanks,

Haran


Obvious homework question and nothing to do with C++ either.

Obviously you weren't paying to much attention in class, had you been
you would have known to convert the tail recursive call into a loop.

john
Oct 19 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.