Another way in which this can be thought is in terms of Tower of Hanoi problem.Just introduce two more stacks of same size as input stack and get the sorted output as result.
On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma <anuragvic...@gmail.com>wrote: > Why not just pop all elements from stack ( O(n) ) and insert it in a self > balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and > inorder traversal ( O(n) )and push elements in stack again. > Time = O(nlog(n) + n) > Space=O(n) (for storing the tree) > > Anurag Sharma > > > > On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha < > jitendra.th...@gmail.com> wrote: > >> Stack can be sorted in O(n^2). >> >> @sankalp: >> Stack can always be sorted. Why do you think it cant be in some cases ? >> >> One can think like insertion sort >> algo : >> 1. for i in (1,n) >> 2. Pop up the top n-1 element and keep nth element in global variable >> say "hold" >> 3. while pushing get the position for "hold" and push it there >> >> for loop will take O(n) and step 2 will take take O(n) time. So overall >> O(n^2) complexity >> Program can be done with recursion using a variable (hence O(1) space). >> But it will use system stack :) >> >> >> Any comments OR better solution is welcomed?? >> >> -- >> Regards >> Jitendra Kushwaha >> MNNIT, Allahabad >> >> -- >> 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<algogeeks%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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Ashish -- 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.
