Re: [algogeeks] Quick short stack space reduction
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 case the recursion depth is always O(logn). On Sat, Jun 5, 2010 at 7:13 AM, sharad kumar sharad20073...@gmail.comwrote: @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 the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Quick short stack space reduction
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 are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Quick short stack space reduction
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 group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Quick short stack space reduction
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 IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Quick short stack space reduction
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, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: 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 IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Quick short stack space reduction
@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 the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
