How to sort a stack using only stack operations?

Question

I found this question on the web.

Given a stack S, write a C program to sort the stack (in the ascending order). We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are:

Push
Pop
Top
IsEmpty
IsFull

I think we can build heap and sort it. What is optimal solution to this?

Answer 1

Pancake sort is another interesting way to do this: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.

Answer 2

If there is no limitation on using other data structures, I would say the minimum heap. whenever popping a element from stack, put into the heap. When popping is done, taking element from the top of heap (minimum of the rest) and pushing it into the stack. Repeating such process until heap is empty.

For creating a heap, the average time is O(nlogn); for deleting elements from heap and putting elements back in ascending order, the average time is O(nlogn) too.

How does it look?

Answer 3

If you don't have any extra information about the stack contents, then you pretty much are stuck just taking all the data out, sorting it, and putting it back in. Heapsort would be great here, as would quicksort or introsort.

Answer 4

Note that Michael J. Barber's answer (see above) is not correct, which forgets to push element back to the stack when it is empty. Correct version is as follows:

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); // !!! must step, otherwise, the stack will eventually be empty after sorting !!!
    }
}

Answer 5

3 stack sort using polyphase merge sort

This should be the fastest way to implement a 3 stack sort. The goal is to end up with an ascending sequence as items are popped from a sorted stack.

Wiki article for polyphase merge sort (using arrays):

http://en.wikipedia.org/wiki/Polyphase_merge_sort

Example C++ code for 3 stack polyphase sort, using pointers, a pointer as a stack pointer for each stack, and a pointer to the end of each run and the end of each stack. The run size pointer is used to keep track of when the run size increments or decrements mid stack. A descending sequence flag is used to keep track if sequences are descending or ascending as data is transferred between stacks. It is initialized at the start, and then alternates after every pair of runs is merged.

typedef unsigned int uint32_t;

static size_t fibtbl[48] =
    {        0,         1,         1,         2,         3,         5,
             8,        13,        21,        34,        55,        89,
           144,       233,       377,       610,       987,      1597,
          2584,      4181,      6765,     10946,     17711,     28657,
         46368,     75025,    121393,    196418,    317811,    514229,
        832040,   1346269,   2178309,   3524578,   5702887,   9227465,
      14930352,  24157817,  39088169,  63245986, 102334155, 165580141,
     267914296, 433494437, 701408733,1134903170,1836311903,2971215073};

// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
    while((hi - lo) > 1){
        size_t i = (lo + hi)/2;
        if(n < fibtbl[i]){
            hi = i;
            continue;
        }
        if(n > fibtbl[i]){
            lo = i;
            continue;
        }
        return i;
    }
    return lo;
}

// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
    if(n < 2)
        return a+n;
    uint32_t *asp = a;                  // a stack ptr
    uint32_t *aer;                      // a end run
    uint32_t *aes = a + n;              // a end
    uint32_t *bsp = b + n;              // b stack ptr
    uint32_t *ber;                      // b end run
    uint32_t *bes = b + n;              // b end
    uint32_t *csp = c + n;              // c stack ptr
    uint32_t *ces = c + n;              // c end
    uint32_t *rsp = 0;                  // run size change stack ptr
    size_t ars = 1;                     // run sizes
    size_t brs = 1;
    size_t scv = 0-1;                   // size change increment / decrement
    bool dsf;                           // == 1 if descending sequence
    {                                   // block for local variable scope
        size_t f = flfib(n);            // fibtbl[f+1] > n >= fibtbl[f]
        dsf = ((f%3) == 0);             // init compare flag
        if(fibtbl[f] == n){             // if exact fibonacci size, move to b
            for(size_t i = 0; i < fibtbl[f-1]; i++)
                *(--bsp) = *(asp++);
        } else {                        // else move to b, c
            // update compare flag
            dsf ^= (n - fibtbl[f]) & 1;
            // move excess elements to b
            aer = a + n - fibtbl[f];
            while (asp < aer)
                *(--bsp) = *(asp++);
            // move dummy count elements to c
            aer = a + fibtbl[f - 1];
            while (asp < aer)
                *(--csp) = *(asp++);
            rsp = csp;                  // set run size change ptr
        }
    }                                   // end local variable block
    while(1){                           // setup to merge pair of runs
        if(asp == rsp){                 // check for size count change
            ars += scv;                 //   (due to dummy run size == 0)
            scv = 0-scv;
            rsp = csp;
        }
        if(bsp == rsp){
            brs += scv;
            scv = 0-scv;
            rsp = csp;
        }
        aer = asp + ars;                // init end run ptrs
        ber = bsp + brs;
        while(1){                       // merging pair of runs
            if(dsf ^ (*asp <= *bsp)){   // if a <= b
                *(--csp) = *(asp++);    //   move a to c
                if(asp != aer)          //   if not end a run
                    continue;           //     continue back to compare
                do                      //   else move rest of b run to c
                    *(--csp) = *(bsp++);
                while (bsp < ber);
                break;                  //     and break
            } else {                    // else a > b
                *(--csp) = *(bsp++);    //   move b to c
                if(bsp != ber)          //   if not end b run
                    continue;           //     continue back to compare
                do                      //   else move rest of a run to c
                    *(--csp) = *(asp++);
                while (asp < aer);
                break;                  //     and break
            }
        }                               // end merging pair of runs
        dsf ^= 1;                       // toggle compare flag
        if(bsp == bes){                 // if b empty
            if(asp == aes)              //   if a empty, done
                break;
            std::swap(bsp, csp);        //   swap b, c
            std::swap(bes, ces);
            brs += ars;                 //   update run size
        } else {                        // else b not empty
            if(asp != aes)              //   if a not empty
                continue;               //     continue back to setup next merge
            std::swap(asp, csp);        //   swap a, c
            std::swap(aes, ces);
            ars += brs;                 //   update run size
        }
    }
    return csp;                          // return ptr to sorted array
}

Example java code for sorting using a custom stack class (xstack) that includes a swap function.

static final int[] FIBTBL =
{        0,         1,         1,         2,         3,         5,
         8,        13,        21,        34,        55,        89,
       144,       233,       377,       610,       987,      1597,
      2584,      4181,      6765,     10946,     17711,     28657,
     46368,     75025,    121393,    196418,    317811,    514229,
    832040,   1346269,   2178309,   3524578,   5702887,   9227465,
  14930352,  24157817,  39088169,  63245986, 102334155, 165580141,
 267914296, 433494437, 701408733,1134903170,1836311903};

// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
    while((hi - lo) > 1){
        int i = (lo + hi)/2;
        if(n < FIBTBL[i]){
            hi = i;
            continue;
        }
        if(n > FIBTBL[i]){
            lo = i;
            continue;
        }
        return i;
    }
    return lo;
}

// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
    if(a.size() < 2)
        return;
    int ars = 1;                        // init run sizes
    int brs = 1;
    int asc = 0;                        // no size change
    int bsc = 0;
    int csc = 0;
    int scv = 0-1;                      // size change value
    boolean dsf;                        // == 1 if descending sequence
    {                                   // block for local variable scope
        int f = flfib(a.size());        // FIBTBL[f+1] > size >= FIBTBL[f]
        dsf = ((f%3) == 0);             // init compare flag
        if(FIBTBL[f] == a.size()){      // if exact fibonacci size,
            for (int i = 0; i < FIBTBL[f - 1]; i++) { //  move to b
                b.push(a.pop());
            }
        } else {                        // else move to b, c
            // update compare flag
            dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
            // i = excess run count
            int i = a.size() - FIBTBL[f];
            // j = dummy run count
            int j = FIBTBL[f + 1] - a.size();
            // move excess elements to b
            do{
                b.push(a.pop());
            }while(0 != --i);
            // move dummy count elements to c
            do{
                c.push(a.pop());
            }while(0 != --j);
            csc = c.size();
        }
    }                                   // end block
    while(true){                        // setup to merge pair of runs
        if(asc == a.size()){            // check for size count change
            ars += scv;                 //   (due to dummy run size == 0)
            scv = 0-scv;
            asc = 0;
            csc = c.size();
        }
        if(bsc == b.size()){
            brs += scv;
            scv = 0-scv;
            bsc = 0;
            csc = c.size();
        }
        int arc = ars;                  // init run counters
        int brc = brs;
        while(true){                    // merging pair of runs
            if(dsf ^ (a.peek() <= b.peek())){
                c.push(a.pop());        // move a to c
                if(--arc != 0)          // if not end a
                    continue;           //   continue back to compare
                do{                     // else move rest of b run to c
                    c.push(b.pop());
                }while(0 != --brc);
                break;                  //   and break
            } else {
                c.push(b.pop());        // move b to c
                if(0 != --brc)          // if not end b
                    continue;           //   continue back to compare
                do{                     // else move rest of a run to c
                    c.push(a.pop());
                }while(0 != --arc);
                break;                  //   and break
            }
        }                               // end merging pair of runs
        dsf ^= true;                    // toggle compare flag
        if(b.empty()){                  // if end b
            if(a.empty())               //   if end a, done
                break;
            b.swap(c);                  //   swap b, c
            brs += ars;
            if (0 == asc)
                bsc = csc;
        } else {                        // else not end b
            if(!a.empty())              //   if not end a
                continue;               //     continue back to setup next merge
            a.swap(c);                  //   swap a, c
            ars += brs;
            if (0 == bsc)
                asc = csc;
        }
    }
    a.swap(c);                          // return sorted stack in a
}

Answer 6

Given those stack operations, you could write a recursive insertion sort.

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); 
    }
}