Jak sortować stos używając tylko operacji stosu?

Biorąc pod uwagę te operacje stosu, można napisać rekurencyjny rodzaj wstawiania.

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); 
    }
}

Można to zrobić rekurencyjnie używając tego samego stosu. O (n^2) Zakodowałem go w C++ , ale konwersja do C jest banalna. Ja po prostu lubię szablony, a Ty otagowałeś swoje pytanie jako C++

template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
  if(element > stack.Top())
  {
    T top = stack.Pop();
    Insert(element, stack);
    stack.Push(top);
  }
  else
  {
    stack.Push(element);
  }
}

template<typename T>
void StackSort(Stack<T>& stack)
{
  if(!stack.IsEmpty())
  {
    T top = stack.Pop();
    StackSort(stack);
    Insert(top, stack);    
  }    
}

Edited to get my vote back! :))

Sortowanie naleśników to kolejny ciekawy sposób na to: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4 .

Zmodyfikowany kod z odpowiedzi T33C
(podane przed Svante poprawiło tag języka z c++ do c):
stack.top() można sprawdzić tylko wtedy, gdy !stack.empty()

void insert(int element, stack<int> &stack) {
    if (!stack.empty() && element > stack.top()) {
        int top = stack.top();
        stack.pop();
        insert(element, stack);
        stack.push(top);
    }
    else {
        stack.push(element);
    } 
}

void sortStack(stack<int> & stack) {
    if (!stack.empty()) {
        int top = stack.top();
        stack.pop();
        sortStack(stack);
        insert(top, stack);
    }
}

3 sortowanie stosu za pomocą sortowania polifazowego merge

To powinien być najszybszy sposób na zaimplementowanie sortowania stosu 3. Celem jest uzyskanie sekwencji rosnącej, ponieważ elementy są wyrzucane z posortowanego stosu.

Artykuł Wiki dla polyphase merge sort (using arrays):

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

Przykładowy kod C++ dla sortowania polifazowego stosu 3, wykorzystujący wskaźniki, wskaźnik jako wskaźnik stosu dla każdego stosu i wskaźnik na koniec każdego biegu i koniec każdego stosu. Wskaźnik run size służy do śledzenia, kiedy Rozmiar run zwiększa się lub zmniejsza w połowie stosu. Znacznik sekwencji malejącej jest używany do śledzenia sekwencji malejących lub rosnących, gdy dane są przesyłane między stosami. Jest inicjowany na początku, a następnie zastępowany po połączeniu każdej pary biegów.

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
}

Przykładowy kod java do sortowania przy użyciu niestandardowej klasy stosu (xstack), która zawiera funkcję swap.

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
}

Jeśli nie masz żadnych dodatkowych informacji o zawartości stosu, to praktycznie utknąłeś po prostu usuwając wszystkie dane, sortując je i wkładając je z powrotem. Heapsort byłby tu świetny, podobnie jak quicksort lub introsort.

Jeśli nie ma ograniczeń w korzystaniu z innych struktur danych, powiedziałbym, że minimalna sterta. za każdym razem, gdy wyskakuje element ze stosu, umieścić w stercie. Gdy popping jest zrobione, biorąc element z góry sterty (minimum z pozostałej) i wepchnięcie go do stosu. Powtarzanie takiego procesu aż sterta będzie pusta.

W przypadku tworzenia sterty średni czas to O(nlogn); w przypadku usuwania elementów ze sterty i przywracania elementów w porządku rosnącym średni czas to O (nlogn).

Jak wygląda?

Zauważ, że odpowiedź Michaela J. Barbera (patrz wyżej) jest nieprawidłowa, co zapomina o odepchnięciu elementu z powrotem do stosu, gdy jest pusty. Poprawna wersja jest następująca:

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 !!!
    }
}

Oto rozwiązanie w Javascript oparte na odpowiedzi udzielonej przez @ OrenD

var org = [4,67,2,9,5,11,3];
var helper = [];

while(org.length > 0){
    var temp = org.pop();
    while((helper.length > 0) && (helper[helper.length-1] < temp)){
        org.push(helper.pop());
    }
    helper.push(temp);
}

while(helper.length > 0){
    org.push(helper.pop());
}

Gra w trzy stosy

Z trzema stosami S (stos źródłowy, stos z niesortowanymi elementami), A, B możesz rozpocząć grę podobną do sortowania scalającego.

Myślę, że jest jasne, że jeśli uporządkowałeś elementy na A i B (w tym samym kierunku, zarówno rosnąco, jak i malejąco), możesz użyć S do scalenia sortowania a i B, a następnie przenieść wynik do, na przykład, B.

Fakt, że masz jakieś elementy na A, B lub S nie przeszkadza ci w używaniu A, B lub S do scalania (o ile masz znacznik bieżącego rozmiaru A, B I S, więc nie przekroczysz). Jeśli twoja procedura przenosi uporządkowane elementy na S, nie jest mózgiem użycie A i B do usunięcia posortowanej Części do A lub B w dowolnym kierunku: możesz umieścić ją w odwrotnej kolejności bezpośrednio do A lub B lub, na przykład, umieścić wszystkie elementy do A, a następnie ponownie odwrócić do B. {]}

Załóżmy, że masz 4 posortowane elementy na A, 16 na B i kilka niesortowanych elementów na S.

A. push (S. pop) i teraz Utwórz 2-elementowe posortowane scalenie. Ponownie B. push (S. pop) i utworzyć inny jeden 2-element posortowane merge. Jeśli scalenia nie są rozdzielone i / lub nie w tym samym kierunku, możesz manipulować elementami w dowolny sposób, aż do osiągnięcia 4-elementowego posortowanego scalenia na B (lub nawet S). Teraz połącz początkowe 4-elementowe posortowane Scalanie z A i tej części na B, aż osiągniesz 8-elementowe posortowane scalanie.

Powtarzasz wszystko, aż utworzysz kolejne 8-elementowe posortowane scalenie. Umieszczasz go w odpowiedniej kolejności na B (lub S) I scalasz, aby uzyskać posortowane scalanie 16-elementowe. Teraz umieść go na A (lub S) i połącz z 16-elementowym scaleniem, które mieliśmy na B cały czas.

Zoptymalizowana implementacja jest trudna, ponieważ trzeba zmniejszyć przenoszenie (przywracanie) posortowanego scalania z jednego stosu na drugi. Jeśli jednak naprawisz i zdecydujesz, co dla ciebie będzie używać A, B I S I wymusisz na przykład: a, aby zawierała mniejszą i większą scaloną część B w porządku malejącym, wtedy algorytm jest prostszy.

Fakt, że musisz przenieść niektóre górne elementy z jednego stosu do drugiego, dodaje stały współczynnik złożoności, ale nigdy nie jest większy niż 2. Poza tym złożoność jest n * log (N) (można osiągnąć 2N-element posortowane scalanie przez scalanie 2 N-element posortowane scalanie, a scalanie wymaga nie więcej niż 2N kroków.)

Implementacja w C# (inne podobne języki są oczywiste)

    void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
    {
        if (n == 0) return;

        if (n == 1)
        {
            mainStack.Push(sourceStack.Pop());
            return;
        }

        int mainSize = n/2;
        int childSize = n - n/2;

        Stacking(sourceStack, mainStack, childStack, mainSize);
        Stacking(sourceStack, childStack, mainStack, childSize);

        while (true)
        {
            while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
            {
                sourceStack.Push(mainStack.Pop());
                mainSize--;
            }

            if (mainSize == 0) break;

            while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
            {
                sourceStack.Push(childStack.Pop());
                childSize--;
            }

            if (childSize == 0) break;
        }

        while (mainSize > 0)
        {
            sourceStack.Push(mainStack.Pop());
            mainSize--;
        }

        while (childSize > 0)
        {
            sourceStack.Push(childStack.Pop());
            childSize--;
        }

        for (int i = 0; i < n; i++)
            mainStack.Push(sourceStack.Pop());
    }

    void SortStack(Stack<int> sourceStack)
    {
        int n = sourceStack.Count();

        // possible optimization: if (n < 2) return;

        Stack<int> mainStack = new Stack<int>();
        Stack<int> childStack = new Stack<int>();

        Stacking(sourceStack, mainStack, childStack, n);

        for (int i = 0; i < n; i++)
            sourceStack.Push(mainStack.Pop());
    }

Gra log (n) stosy

Powyższa procedura może być uproszczone, jeśli możesz używać co najwyżej stosów log(n). Ta liczba stosów nie oznacza, że kiedykolwiek użyjesz dodatkowej przestrzeni większej niż kolejność n. po prostu zaznacz stosy, które będą używane do łączenia 1, 2, 4... żywioły. W tym przypadku nie zależy ci na kolejności, ponieważ scalanie części 2^n będzie zawsze sortowane w tym samym kierunku. Jednak to rozwiązanie tylko omija fakt, że ograniczasz się do korzystania z operacji push i pop; poza tym jest równoważne z scalanie sortowania we wszystkich aspektach. W istocie, jeśli liczba stosów nie jest ograniczona, możesz łatwo emulować szybkie sortowanie.

/* the basic idea is we go on
 *  popping one element (o) from the original stack (s) and we
 *  compare it with the new stack (temp)
 * if o (the popped element from original stack)
 *  is < the peek element from new stack temp
 * then we push the new stack element to original stack
 *  and recursively keep calling till temp is not empty
 *  and then push the element at the right place.
 * else we push the element to the new stack temp
 *  (o >= new temp stack.
 *
 * Entire logic is recursive.
 */

public void sortstk( Stack s )
{
    Stack<Integer> temp = new Stack<Integer>();

    while( !s.isEmpty() )
    {
        int s1 = (int) s.pop();

        while( !temp.isEmpty() && (temp.peek() > s1) )
        {
            s.push( temp.pop() );
        }
        temp.push( s1 );
    }

    // Print the entire sorted stack from temp stack
    for( int i = 0; i < temp.size(); i++ )
    {
        System.out.println( temp.elementAt( i ) );
    }
}

Myślę, że sortowanie bąbelków może działać na stosie z rekurencją.

   void sortStack(stack<int>& st){
        bool flag = true;
        int n = st.size();
        for(int i = 1; i <= n - 1 && flag; i++){
            flag = false;
            bubbleSortStack(st, flag, i);
        }
    }
    void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
        if(st.size() == endSize)
            return;
        int val = st.top();
        st.pop();
        if(val > st.top()){
            flag = true;
            int tmp = st.top();
            st.push(val);
            val = tmp;
        }
        bubbleSortStack(st, flag);
        st.push(val);
    }