Wie sortiere ich einen Stapel nur mit Stapeloperationen?

Lesezeit: 13 Minuten

Ich habe diese Frage im Internet gefunden.

Schreiben Sie bei gegebenem Stack S ein C-Programm, um den Stack (in aufsteigender Reihenfolge) zu sortieren. Wir dürfen keine Annahmen darüber treffen, wie der Stack implementiert ist. Die einzigen zu verwendenden Funktionen sind:

Push
Pop
Top
IsEmpty
IsFull

Ich denke, wir können Haufen bauen und sortieren. Was ist die optimale Lösung dafür?

  • Geben Sie bitte einen Link an. Wie bereits erwähnt, könnten Sie einfach in eine beliebige andere Struktur kopieren, diese sortieren und wieder hineinkopieren. O(1) Zusätzliche Speichernutzung ist die kritische Anforderung.

    – Kartoffelklatsche

    28. Januar 2011 um 8:43 Uhr

  • O(1) zusätzlicher Speicher ist nachweislich unmöglich. Wenn die unteren beiden Elemente des Stapels ausgetauscht werden müssen, müssen alle darüber liegenden Elemente in einen zusätzlichen Speicher verschoben werden. Das ist O(N).

    – MSalter

    28. Januar 2011 um 8:46 Uhr

  • Warum zum Teufel willst du einen Stapel sortieren?

    – lepi

    28. Januar 2011 um 8:48 Uhr

  • @MSalters: Ja. Ich denke, die einzig guten Antworten auf diese Frage sind “kann nicht” und “duh”.

    – Kartoffelklatsche

    28. Januar 2011 um 8:49 Uhr

  • Für mich klingt es nach dem Problem “Der Turm von Hanoi”: en.wikipedia.org/wiki/Towers_of_Hanoi. Die Aufgabe ist etwas anders, aber ich denke, man könnte damit anfangen.

    Benutzer346034

    28. Januar 2011 um 9:25 Uhr

Benutzer-Avatar
OrenD

Angenommen, die einzige hier erlaubte Datenstruktur ist der Stack, dann könnten Sie 2 Stacks verwenden.

Iterieren Sie, bis der ursprüngliche Stapel leer ist, und entfernen Sie bei jeder Iteration ein Element aus dem ursprünglichen Stapel, während das oberste Element im zweiten Stapel größer als das entfernte Element ist, entfernen Sie den zweiten Stapel und schieben Sie es auf den ursprünglichen Stapel. Jetzt können Sie das Element, das Sie ursprünglich vom ursprünglichen Stapel entfernt haben, auf den zweiten Stapel verschieben.

Die zeitliche Komplexität dieses Ansatzes beträgt O(N^2).

C-Code zur Implementierung dieses Algorithmus wäre (entschuldigen Sie meine eingerosteten C-Kenntnisse):

void SortStack(struct Stack * orig_stack)
{
  struct Stack helper_stack;
  while (!IsEmpty(orig_stack))
  {
    int element = Pop(orig_stack);
    while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
    {
      Push(orig_stack, Pop(&helper_stack));
    }
    Push(&helper_stack, element);
  }
  while (!IsEmpty(&helper_stack))
  {
    Push(orig_stack, Pop(&helper_stack));
  }
}

  • Ist das nicht nur eine Einfügesortierung, bei der Sie manuell einen Stapel verwenden, um die Rekursion zu handhaben?

    – Michael J. Barbier

    28. Januar 2011 um 9:54 Uhr

  • Das O(n^2) Komplexität ist hier fraglich, weil ein einzelnes Element ein- und austreten kann orig_stack mehrmals. Daher die Anzahl der Iterationen des Äußeren while Schleife wird viel mehr sein als n.

    – Nikita Rybak

    28. Januar 2011 um 10:10 Uhr


  • @Nikita: Versuchen wir, uns das Worst-Case-Szenario anzusehen (in Bezug auf die Häufigkeit, mit der ein Element zwischen den Stapeln hin und her geht). Dies wäre der Fall, wenn der ursprüngliche Stapel bereits sortiert ist. Schauen wir uns nun das Element an, das am meisten „reist“. Dies wäre das oberste Element im ursprünglichen Stapel und würde O(n) mal “reisen”. Wenn wir uns auf die restlichen Elemente ausdehnen, haben wir ungefähr 2 * (1 + 2 + 3 + … + n) “Reisen”. Das heißt, wir erhalten O(n^2).

    – OrenD

    28. Januar 2011 um 10:35 Uhr

  • @OrenD Wie genau hast du das Worst-Case-Szenario identifiziert? Zum Beispiel für Standard-Schnellsortierung (mit Drehpunkt in der Mitte), Worst-Case O(n^2) Szenario ist sehr knifflig. Es werden sowohl sortierte als auch invers sortierte Arrays ausgeführt O(n*logn) da, aber das beweist nichts.

    – Nikita Rybak

    28. Januar 2011 um 10:38 Uhr


  • In Ihrer Antwort sagten Sie: “Ein Element aus dem ursprünglichen Stapel entfernen, während das oberste Element im zweiten Stapel größer als das entfernte Element ist, den zweiten Stapel entfernen und auf den ursprünglichen Stapel verschieben.” Aber Ihre While-Schleife-Bedingung ist falsch: Top(&helper_stack) < element Wieso den?

    – sam_k

    31. Juli 2015 um 2:25 Uhr

Benutzer-Avatar
Michael J. Barbier

Angesichts dieser Stapeloperationen könnten Sie eine rekursive Einfügesortierung schreiben.

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

  • +1 Ich mag diese Lösung, sie missbraucht den Aufrufstapel als zusätzliche Datenstruktur 🙂

    – Axarydax

    28. Januar 2011 um 13:49 Uhr

Benutzer-Avatar
T33C

Dies kann rekursiv mit demselben Stack erfolgen. O(n^2) Ich habe es in C++ codiert, aber die Konvertierung nach C ist trivial. Ich mag einfach Vorlagen und Sie haben Ihre Frage als C++ markiert

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

  • Nein, dein Code ist nicht korrekt. Ihr erstes Element wird niemals seinen Platz wechseln.

    – UmmaGumma

    28. Januar 2011 um 9:17 Uhr

  • Entschuldigung, Ihre Lösung ist völlig richtig. Aber jetzt kann ich meine Ablehnung nicht rückgängig machen, bis Sie etwas in Ihrem Beitrag bearbeiten. Bearbeiten Sie etwas und ich werde Ihre Lösung positiv bewerten.

    – UmmaGumma

    28. Januar 2011 um 10:05 Uhr

  • @Ashot Martirosyan – Ich habe bearbeitet. Vielen Dank. Ich habe nicht kompiliert, aber die Idee sollte richtig sein.

    – T33C

    28. Januar 2011 um 10:29 Uhr

  • Ich würde sagen, es gibt implizit ein weiterer Stack, obwohl die Idee praktikabel erscheint.

    – Nikita Rybak

    28. Januar 2011 um 10:57 Uhr

Pancake Sort ist eine weitere interessante Möglichkeit, dies zu tun: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.

Benutzer-Avatar
SW

Geänderter Code aus der Antwort von T33C
(vorgegeben, bevor Svante das Sprach-Tag von c++ auf c korrigierte):
stack.top() kann nur geprüft werden, ob !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);
    }
}

  • (abgesehen von inkonsistenter Einrückung -) Was ist die Absicht mit diesem Post?

    – Graubart

    6. August 2016 um 17:24 Uhr

  • Wenn nur ein Element im Stack vorhanden ist, prüft der Ursprungscode von T33c nicht, ob der Stack beim Einfügen leer ist, wodurch eine Ausnahme in der Insert-Funktion ausgelöst wird.

    – SW

    20. August 2016 um 20:08 Uhr


  • top() Wenn stack darf leer sein: Kein schlechter Fang.

    – Graubart

    21. August 2016 um 10:52 Uhr

3-Stack-Sortierung unter Verwendung von Polyphase-Merge-Sortierung

Dies sollte der schnellste Weg sein, eine 3-Stapel-Sortierung zu implementieren. Die Zeitkomplexität ist O(n log(n)). Das Ziel ist es, eine aufsteigende Sequenz zu erhalten, wenn Elemente aus einem sortierten Stapel entnommen werden. Der Ursprung für diese Methode war die Verwendung von Polyphase Merge Sort auf alten Mainframe-Bandlaufwerken, die rückwärts lesen konnten (um Rückspulzeit zu vermeiden), ähnlich wie beim Stapeln, da während des Sortierens vorwärts geschrieben und rückwärts gelesen wurde.

Wiki-Artikel für Polyphase Merge Sort (mithilfe von Arrays):

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

Beispiel-C++-Code für eine mehrphasige Sortierung mit 3 Stapeln unter Verwendung von Zeigern, einem Zeiger als Stapelzeiger für jeden Stapel und einem Zeiger auf das Ende jedes Laufs und das Ende jedes Stapels. Der Laufgrößenzeiger wird verwendet, um zu verfolgen, wann die Laufgröße in der Mitte des Stapels inkrementiert oder dekrementiert wird. Ein Flag für absteigende Sequenzen wird verwendet, um zu verfolgen, ob Sequenzen absteigend oder aufsteigend sind, wenn Daten zwischen Stapeln übertragen werden. Es wird am Anfang initialisiert und wechselt dann, nachdem jedes Paar von Läufen zusammengeführt wurde.

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

Java-Beispielcode zum Sortieren mithilfe einer benutzerdefinierten Stack-Klasse (xstack), die eine Swap-Funktion enthält.

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
}

Die benutzerdefinierte Java-Stack-Klasse:

class xstack{
    int []ar;                               // array
    int sz;                                 // size
    int sp;                                 // stack pointer
    public xstack(int sz){                  // constructor with size
        this.ar = new int[sz];
        this.sz = sz; 
        this.sp = sz;
    }
    public void push(int d){
        this.ar[--sp] = d;
    }
    public int pop(){
        return this.ar[sp++];
    }
    public int peek(){
        return this.ar[sp];
    }
    public boolean empty(){
        return sp == sz;
    }
    public int size(){
        return sz-sp;
    }
    public void swap(xstack othr){
        int []tempar = othr.ar;
        int tempsz = othr.sz;
        int tempsp = othr.sp;
        othr.ar = this.ar;
        othr.sz = this.sz;
        othr.sp = this.sp;
        this.ar = tempar;
        this.sz = tempsz;
        this.sp = tempsp;
    }
}

  • (abgesehen von inkonsistenter Einrückung -) Was ist die Absicht mit diesem Post?

    – Graubart

    6. August 2016 um 17:24 Uhr

  • Wenn nur ein Element im Stack vorhanden ist, prüft der Ursprungscode von T33c nicht, ob der Stack beim Einfügen leer ist, wodurch eine Ausnahme in der Insert-Funktion ausgelöst wird.

    – SW

    20. August 2016 um 20:08 Uhr


  • top() Wenn stack darf leer sein: Kein schlechter Fang.

    – Graubart

    21. August 2016 um 10:52 Uhr

Benutzer-Avatar
Vorlagentypdef

Wenn Sie keine zusätzlichen Informationen über den Inhalt des Stacks haben, müssen Sie praktisch nur alle Daten herausnehmen, sortieren und wieder einfügen. Heapsort wäre hier großartig, ebenso wie Quicksort oder Introsort.

  • Wenn die Idee ist, während des Interviews ein C-Programm zu schreiben, wäre Bubblesort eine gute Wahl.

    – Kartoffelklatsche

    28. Januar 2011 um 8:50 Uhr

  • @Potatoswatter- Können Sie die Gründe dafür näher erläutern? Ich würde mir vorstellen, dass alle anderen O(n^2)-Sortierungen einfacher zu schreiben sind (z. B. Einfügung oder Auswahl) und dass eine O(n lg n)-Sortierung wie Heapsort oder Mergesort vergleichsweise schwierig wäre.

    – Vorlagentypdef

    28. Januar 2011 um 8:56 Uhr

1366480cookie-checkWie sortiere ich einen Stapel nur mit Stapeloperationen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy