u r using merge(), which is implementaion specific!!
Cheers,
siva.
On 5/5/06, harsh <[EMAIL PROTECTED]> wrote:
This is clearly O(N*N)
I will give you an O(N*log(N)) algorithm..
Stack sort(Stack S, int N){ // N is the number of elements in the
stack
Stack s1 = new Stack();
for (int i=0;i<N/2;i++){ s1.add(S.top()); S.pop(); }
Stack sort1 = sort(s1, N/2);
Stack sort2 = sort(S, N - N/2);
Stack final = merge(sort1, sort2); //do standard 2-way merge
}
Amit Bhatnagar wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
