Sorting a stack in ascending order in C, using two stacks

Question

I was given a task to sort numbers in stack a of integers in ascending order using two stacks a and b.

Using eleven operations:

1. sa : swap a - swap the first 2 elements at the top of stack a
2. sb : swap b - swap the first 2 elements at the top of stack b.
3. ss : sa and sb at the same time.
4. pa : push a - take the first element at the top of b and put it at the top of a.
5. pb : push b - take the first element at the top of a and put it at the top of b.
6. ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one.
7. rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one.
8. rr : ra and rb at the same time.
9. rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one.
10. rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one.
11. rrr : rra and rrb at the same time.

My sorting function

void    sorts_stack(stack *a, stack *b)
{
    int     srt;

    srt = is_not_sorted(a);
    if (srt)
    {
        if (a->list[srt] == top(a) && a->list[srt] > a->list[0])
        {
            rotate_ra_rb(a->list, a->size); //ra : rotate a
            putstr("ra\n");
        }
        else if (a->list[srt] == top(a) && a->list[srt] > a->list[srt - 1])
        {
            swap_sa_sb(a->list, a->size);//sa : swap a
            putstr("sa\n");
        }
        else if (a->list[srt] > a->list[srt - 1])
        {
            putstr("pb\n"); //pb : push b
            push_pb(a, b);
        }
        sorts_stack(a, b);
    }
    else if (b->size > 0)
    {
        if (top(a) < top(b))
        {
            push_pa(a, b); //pa : push a
            putstr("pa\n");
        }
        else if ((top(a) > top(b)) && b->size != 0)
        {
            push_pa(a, b); //pa : push a
            putstr("pa\n");
        }
        sorts_stack(a, b);
    }
}

my function sort the stack, I think it takes too many steps to sort. I need suggestions or advice on how to make it sort the stack with less steps taken. complete online code

Answer 1

Given two stacks A and B, where A is filled with a random permutation of elements and B is empty, and one temporary variable T able to hold one element (and a counter but the counter doesn't count) you can sort A in ascending order into B by:

1. move all elements from A to B but keep the largest element in T
2. move all elements from B to A
3. put element in T on the stack B
4. Loop until A is empty
   1. move all elements from A to B but keep the largest element in T
   2. move all elements from B to A except the biggest one(s) on the bottom (here is the place where the counter comes handy to keep the number of already sorted elements in B)
   3. put element in T on the stack B

You can (and should) put all of it in a single loop, of course.

Answer 2

This is really a two queue problem, since the rotate operations effectively turn a stack into a queue. In this case a bottom up merge sort can be performed, which would be relatively fast.

Using a linked list (instead of an array) to implement the stack / queue would speed up the rotates.

---

Bottom up merge sort for 2 queues:

Initial split: Pop elements off the original queue, and appended elements alternately to the original and temporary queue. Set queue size to number of elements popped off original queue. Set sorted run size to 1.

Merge pass: using sorted run size to determine size of runs, merge runs from each queue, alternating the merged output between the original and temporary queues. Double the run size, stop if run size >= queue size.