Algorithmus zum Sortieren des Stapels an Ort und Stelle

Question

Welche Sortieralgorithmen wären gut, um einen Stack für die Platzeffizienz zu sortieren? Ich muss einen Stapel an Ort und Stelle sortieren. Auch mein Verständnis von "In Place" -Algorithmen war, dass sie keine zusätzlichen Datenstrukturen verwenden - ist das korrekt?

Ich weiß, das ist ähnlich wie this question, aber ich frage mich, ob es für Stacks anders wäre? Ich weiß Stacks können nur eine Art von Linkedlist sein, aber macht die Tatsache, dass Sie nur auf die Top-Änderung zugreifen können, wie Sie es tun würden?

Answer 1

Sie müssen das "in-place" -Kennzeichen überspringen, wenn Sie den Stapel nur mit Stapeloperationen sortieren wollen (Sie müssen einen anderen Stapel haben). Ein In-Place-Algorithmus ist ein Algorithmus, der seine Eingabe unter Verwendung anderer Datenstrukturen transformiert. Für intermediäre/temporäre Variablen ist jedoch eine kleine Menge zusätzlichen Speicherplatzes zulässig.

Wenn Sie die „in-place“ Qualifier auslassen Sie Ihre Antwort finden Sie hier: How to sort a stack using only stack operations? (sortiert einen Stapel einen zusätzlichen Helfer Stack)

Wenn Sie die Qualifier dann das Sortieren des Stapels beibehalten auf die nur möglich ist, Implementierungsebene und nicht mithilfe von Stapeloperationen.

Answer 2

Es gibt eine alternative Definition für in-Place-Art das bedeutet nur die sortierten Daten endet wieder im gleichen Behälter nach oben (in diesem Fall ein Stapel), dass die unsortierte Daten, die ursprünglich in gespeichert wurde.

Kommen wir zurück zu den Originalfrage, die einzige Möglichkeit, auf das letzte Element eines Stapels zuzugreifen und/oder dieses zu ändern, ist das Abspringen aller anderen Elemente, was an anderer Stelle O (n-1) Platz erfordert, wobei das einfachste ein Array ist.

Wenn der Stapel als verkettete Liste implementiert ist, kann eine Sortierung nach Art einer verknüpften Liste verwendet werden. Dies wäre jedoch eine listorientierte Sortierung mit anderen Operationen als den Standard-Stapeloperationen peek, pop und push.