@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 <[email protected]> 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 <[email protected]> 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
>> <[email protected]>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 <[email protected]> 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 <[email protected]> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
