Removing Tail recursions in quicksort

[nkharan]

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

 

[Greg]

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

 

[John Harrison]

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