Sortieren mit Nur-Lese-Stapeln

14

Betrachten Sie die folgende Einstellung:

  • Wir erhalten einen Stapel der Elemente enthält .nsn
  • Wir können eine konstante Anzahl von zusätzlichen Stapeln verwenden.Ö(1)
  • Wir können die folgenden Operationen auf diese Stapel anwenden:
    1. Überprüfen Sie, ob ein Stapel leer ist.
    2. Vergleichen Sie die Top-Artikel von zwei Stapeln,
    3. lösche den obersten Gegenstand in einem Stapel,
    4. Drucke den obersten Gegenstand in einem Stapel,
    5. Kopieren Sie das oberste Element eines Stapels in einen anderen Stapel.
    6. Kopieren Sie den Inhalt eines Stapels auf einen anderen Stapel.

Beachten Sie, dass dies die einzigen Operationen sind, die zulässig sind. Wir können keine Gegenstände tauschen und wir dürfen keine Gegenstände auf einen der Stapel schieben, mit Ausnahme des Kopierens des obersten Gegenstands in einen Stapel (danach wird der vorherige Inhalt des Zielstapels verworfen und enthält nur den kopierten Gegenstand). .

Hier ist ein Algorithmus zum Sortieren der Stapel mit -Vergleichen:Ö(n2)

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Können wir es besser machen?

Gibt es ein Programm, das die sortierte Liste der Elemente in den Stapeln nur mit -Vergleichen druckt ?Ö(nLogn)

Siddharth
quelle
2
Es hört sich so an, als ob sich die Register wie Stapel verhalten. Es hört sich so an, als würden Sie über Push- und Pop-Operationen sprechen. Sind das deine Fragen? Wie würden Sie einen Stapel sortieren, indem Sie mehrere Stapel und Stapeloperationen verwenden?
Wolfdawn
2
Mit Registern können Sie: einfach jede Zahl in ein Register setzen ( ) und dann einen üblichen Sortieralgorithmus anwenden ( ). O ( n ) O ( n lg n )nO(n)O(nlgn)
Kaveh
1
Möchten Sie -Register verwenden? Ansonsten ist das Problem, wie von Kaveh kommentiert, banal. Ö(1)
Yuval Filmus
1
Bitte schön. Ich dachte, dass wir eine Reihe von Stacks bekommen, nicht nur einen, ich werde es reparieren.
Kaveh
2
@akappa, bist du sicher, dass diesbezüglich verwendet werden kann? Wir können keine willkürlich verlorene Größe größer als 1 halten. Müssen Sie die sortierten Blöcke nicht speichern?
Kaveh

Antworten:

1

Ich denke, ich kann jetzt eine nichttriviale Untergrenze demonstrieren. Die Idee ist, ein solches Programm mit einer Familie von Vergleichsverzweigungsprogrammen zu implementieren. Die "Nur-Lese" -Annahme bedeutet, dass unsere Familie von Verzweigungsprogrammen nur wenig Platz benötigt, dh . Dann wenden wir die untere Grenze S T = Ω ( n 2 ) an , die von Borodin et al. in "Ein Time-Space-Tradeoff für das Sortieren auf nicht vergessenen Maschinen." Dies gibt uns eine Untergrenze von n 2 / log n für die Zeit.Ö(Logn)ST=Ω(n2)n2/logn

Im Detail: Auf die obige Operation 5 können wir verzichten. Wenn wir schon die Köpfe zweier Listen vergleichen und den Kopf einer Liste ausdrucken können, brauchen wir den Kopf einer Liste nicht in einem bestimmten Register zu isolieren. Angenommen, wir sehen, dass jedes Register in der Maschine immer nur eine letzte Teilzeichenfolge der Eingabe speichert.

Angenommen, unser Registerprogramm hat Codezeilen und k Register, X 1 , , X k .kX1,,Xk

Fix . Wir konstruieren das Vergleichsverzweigungsprogramm für Zeichenketten der Länge n wie folgt. Erstellen Sie einen Knoten für jedes Tupel ( i , d 1 , , d k ) mit 1 i und 0 d 1 , , d kn . Die Idee ist, dass Berechnungen in der Registermaschine Pfaden im Verzweigungsprogramm entsprechen und wir uns am Knoten ( i , d 1 , , dnn(i,d1,,dk)1i0d1,,dkn , wenn wir anLinie sind i im Register Maschine und die Länge des Strings gespeichert in X i ist d i . Nun müssen wir die gerichteten Kanten des Verzweigungsprogramms definieren(i,d1,,dk)iXidi

Wenn Zeile von der Form isti

wenn dann gehe zu i 1 sonst gehe zu i 2Xu<Xvi1i2

dann für all , den Knoten ( i , d 1 , ... , d k ) wird durch Vergleichen des markierten d u ' ten und d v -te Element der Eingabe, und die "wahren" edge gehen zu müssen , um ( i 1 , d 1 , , d k ) und die "falsche" Kante zu ( i 2 , d 1 , , d kd1,,dk(i,d1,,dk)dudv(i1,d1,,dk) .(i2,d1,,dk)

Wenn Zeile von der Form istich

, gehe zur Linie i 'X1teinichl(X2)ich

dann gibt es einen Pfeil von einem beliebigen Knoten zu ( i ' , d 2 - 1 , , d k ) .(ich,d1,,dk)(ich,d2-1,,dk)

Wenn Zeile von der Form istich

, gehe zur Linie i 'print(head(Xu))i

dann gibt es einen Pfeil von jedem Knoten bis ( i ' , d 1 , ... , d k ) , die durch den gekennzeichnet ist d u -ten Knoten des Einganges.(i,d1,,dk)(i,d1,,dk)du

Hoffentlich machen diese Beispiele deutlich, wie ich mein Verzweigungsprogramm aufbauen will. Wenn alles gesagt und getan ist , diese Verzweigung Programm hat höchstens Knoten, so dass es Raum hat O ( log n )nkÖ(Logn)

Siddharth
quelle
0

Können Sie Elemente zählen? Dann, denke ich, gibt es eine ziemlich einfache Mergesort-Implementierung. Wenn Sie zusätzliche Symbole auf den Stapel legen könnten, könnten Sie dies mit 3 Stapeln wie folgt lösen:

Wenn wir nur ein Element haben, ist die Liste bereits sortiert. Nehmen wir nun an, wir haben die obere Hälfte des Stapels bereits sortiert. Wir können die obere Hälfte (in umgekehrter Reihenfolge) auf den zweiten Stapel kopieren und ein Trennsymbol darauf platzieren. Jetzt haben wir wieder 3 Stapel (da wir die bereits sortierten Symbole unterhalb des Trennsymbols ignorieren können) und können die untere Hälfte sortieren. Schließlich können wir die sortierte untere Hälfte in umgekehrter Reihenfolge auf einen dritten Stapel kopieren und beide Hälften wieder zum ursprünglichen Stapel zusammenführen.

Alle Operationen kosten lineare Zeit, daher haben wir die Liste in O ( n log n ) sortiertO(nLogn)

(Beachten Sie, dass wir aufgrund der Trennsymbole Stapel der Größe benötigen , dies kann jedoch leicht durch Verwendung eines anderen Stapels korrigiert werden.)nLogn


Da Sie keine neuen Elemente auf den Stapel legen können, können Probleme an den Trennungspunkten auftreten. Um dies zu lösen, können Sie mit einigen zusätzlichen Stapeln Folgendes tun:

n2logn

lognccnlogn+cn2logn2+cn4logn4+ ...=O(nlogn)O(nlogn)

cero
quelle
Ich bin mir nicht sicher ob ich das verstehe. Wie können wir zum Beispiel die obere Hälfte des Stapels in umgekehrter Reihenfolge auf einen anderen Stapel kopieren, wenn wir niemals ein Element auf einen Stapel schieben können?
Siddharth
Wir können kein neues Element auf einen Stapel schieben, aber gemäß 5 können wir das oberste Element eines Stapels auf einen anderen schieben. Das Kopieren des Stapels in umgekehrter Reihenfolge erfordert also höchstens eine lineare Zeit. Ich nehme an, das war nicht das, wonach Sie gefragt haben?
Cero
Wie in der Frage erläutert, können Sie nichts auf andere Elemente schieben.
Kaveh