Hi all,
Please correct me if I am wrong. Since quick sort is in-place
sort, there is no difference in stack space whichever order you do it. In
the worst case the stack depth can be O(n) unless you convert the quick sort
of longer sub-array to iteration instead of recursion in which
Actually he means the case when you implement quicksort using stacks.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you
in quick short each time list is divided into two part ..suppose shorter one
and longer one . it is said that shorting smaller sublist first reduces
stack space . why so ?
thnx
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
if you short the larger one first, then the smaller one will be in the
stack for a long time. Which is wasting stack space.
Now stop shorting and start sorting ! :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
if u sort the larger one first one then smaller one will be on stack for a
long time on the other hand if u sort smaller one first then larger one will
be in stack for long time. so more space is wasted is 2nd case so we shd
sort larger first. correct me if i am wrong plzzz
On 4 June 2010 18:08,
@divya,in second case longer one will be in stack for shorter time(not
longer)bcoz it will take less time to sort small sequence so stack space for
shorter one will be freed earlier,otherwise that space has to wait for the
longer time
--
You received this message because you are subscribed to
