P: n/a

Hey,
Here is the pseudocode of quicksort. It can be observed that there
are as many as (n1) 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:n1], low, high) recursive
Input: L[0:n1] (a list of size n), low, high (integers)
Output: L[low:high] is sorted
if high > low then
Partition(L[0:n1], low, high, position)
QuickSort(L[0:n1], low, position  1)
QuickSort(L[0:n1], position + 1, high)
endif
end QuickSort
thanks,
Haran  
Share this Question
P: n/a
 nk*****@gmail.com wrote: Hey, Here is the pseudocode of quicksort. It can be observed that there are as many as (n1) 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:n1], low, high) recursive Input: L[0:n1] (a list of size n), low, high (integers) Output: L[low:high] is sorted if high > low then Partition(L[0:n1], low, high, position) QuickSort(L[0:n1], low, position  1) QuickSort(L[0:n1], 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  
P: n/a
 nk*****@gmail.com wrote: Hey, Here is the pseudocode of quicksort. It can be observed that there are as many as (n1) 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:n1], low, high) recursive Input: L[0:n1] (a list of size n), low, high (integers) Output: L[low:high] is sorted if high > low then Partition(L[0:n1], low, high, position) QuickSort(L[0:n1], low, position  1) QuickSort(L[0:n1], 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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2623
 replies: 2
 date asked: Oct 19 '05
