Rahul K wrote:
> Given a stack how can I sort it in ascending order. No assumption are
> to be made about the implementation of the stack. The only functions
> available are push(), pop(), top(), isEmpty(), isFull(). A optimized
> solution is highly appreciable.
I believe the following solution may work:
This sorts the stack in place...
Sort(stack S)
{
if( isEmpty(S))
return; /*STack with no elements is sorted */
/* Insert stack top in sorted rest of the stack */
element a=pop(S);
insert(Sort(S) , a);
}
Insert( stack S, element a)
/* This inserts an element a in a sorted stack S*/
{
if isEmpty(S)
push(S,a);
return;
element b=pop(S);
if(a<b) /* a is less then the least elemnt in stack; dont
disturb existing order*/
push(S,b);
push(S,a);
return;
/* Here a is greater than stack's min element; so first insert a at its
proper place; then push b*/
insert(S,a);
push(S,b);
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
