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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
