@anurag I meant the sorting without using any auxiliary data structure .Also we have to put the element in the tree and carry out a traversal for every element we insert in the tree .This takes O(n*logn) time , If one can sort the elements using a stack in O(n) time , we better sort with this method , say "Stack sort" Moral:-No (comparison based )sorting method exists for which time complexity is less than O(n*log n) also , without using any auxialliary data structure , we cannot create all the permutations of the stack Refer Donald knuth's TAOCP for more details 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. > -- 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.
