@Srinivas: Sorry for the confusion. But if we have a stack {5,8,3,4,2} with 5 as the last input,ie,top, do we have to arrange the stack such that s={2,3,4,5,8}with 2 as the top? if I am getting it correct,then shouldn't your algo be modified slightly as follows:? reverse(stack *s){ IsEmpty(s) return; top = pop(s); reverse(s); ascending(s, top); } ascending(stack *s, int top){ IsEmpty(s){ push(top); return; } i = pop(s); if(i > top){
push(top); } else{ ascending(s, top); push(i); } } On Sat, Sep 11, 2010 at 7:04 PM, ashita dadlani <ash....@gmail.com> wrote: > @Srinivas: > shouldn't it be: > > i = pop(s); > if(i > top){ > ascending(s, i); > push(top); > } > else{ > > ascending(s, top); > push(i); > } > > > On Sat, Sep 11, 2010 at 6:52 PM, ashita dadlani <ash....@gmail.com> wrote: > >> >> else{ >> ascending(s, i); >> push(top); >> } >> } >> @swinivas:why have you used ascending(s,i) here? >> On Sat, Sep 11, 2010 at 6:40 PM, Srinivas >> <lavudyasrinivas0...@gmail.com>wrote: >> >>> reverse(stack *s){ >>> IsEmpty(s) >>> return; >>> top = pop(s); >>> reverse(s); >>> ascending(s, top); >>> } >>> ascending(stack *s, int top){ >>> IsEmpty(s){ >>> push(top); >>> return; >>> } >>> i = pop(s); >>> if(i > top){ >>> ascending(s, top); >>> push(i); >>> } >>> else{ >>> ascending(s, i); >>> push(top); >>> } >>> } >>> >>> Please let me know if it wont work..thanks >>> >>> On Jul 18, 6:58 am, xyombie <brianbl...@gmail.com> wrote: >>> > What about a quick sort O(log n) >>> > >>> > void sort_stack(Stack *src, Stack *dst) >>> > { >>> > if(! src->IsEmpty() ) >>> > { >>> > Stack smaller, larger; >>> > int pivot = src->Pop(); >>> > >>> > while(! src->IsEmpty() ) >>> > { >>> > int tmp = src->Pop(); >>> > if(tmp < pivot) >>> > smaller->Push(tmp); >>> > else >>> > larger->Push(tmp); >>> > } >>> > >>> > sort_stack(smaller, dst); >>> > dst->Push(pivot); >>> > sort_stack(larger, dst); >>> > } >>> > >>> > } >>> > >>> > On Jul 17, 9:28 am, vijay <auvija...@gmail.com> wrote: >>> > >>> > > Write a C program to sort a stack in ascending order. You should not >>> > > make any assumptions about how the stack is implemented. The >>> following >>> > > are the only >>> > > functions that should be used to write this program: >>> > > Push | Pop | Top | IsEmpty | IsFull >>> > > The algorithm is O(N^2) and appears below. >>> > > Do we have any other better solution which is less than O(n * n) ? >>> > >>> > > void sort_stack(Stack * src, Stack * dest) >>> > > { >>> > > while (!src->IsEmpty()) >>> > > { >>> > > Int tmp = src->Pop(); >>> > > while(!dest->IsEmpty() && dest->Top() > tmp) >>> > > { >>> > > src->Push(dest->Pop()); >>> > > } >>> > > dest->Push(tmp); >>> > > } >>> > >>> > > } >>> >>> -- >>> 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.