Warum sortieren wir lieber die kleinere Partition einer Datei und schieben nach der Partitionierung den größeren auf den Stack für Quicksort (nicht-rekursive Implementierung)? Dadurch verringert sich die Platzkomplexität von Quicksort O (log n) für zufällige Dateien. Könnte jemand es ausarbeiten?
Wie Sie wissen, partitionieren Sie bei jedem rekursiven Schritt ein Array. Schieben Sie den größeren Teil auf den Stapel, fahren Sie mit dem kleineren Teil fort.
Weil der, mit dem Sie arbeiten, der kleinere ist, ist er höchstens halb so groß wie der, mit dem Sie vorher gearbeitet haben. Für jeden Bereich, den wir auf den Stapel schieben, halbieren wir die Größe des Bereichs, mit dem wir arbeiten.
Das bedeutet, dass wir nicht mehr als log n range auf den Stack schieben können, bevor der Bereich, mit dem wir arbeiten, die Größe 1 erreicht (und daher sortiert ist). Dies begrenzt die Menge des Stapels, die wir benötigen, um den ersten Abstieg zu vollenden.
Wenn wir mit der Bearbeitung der "großen Teile" beginnen, ist jeder "große Teil" B (k) größer als der "kleine Teil" S (k), der zur gleichen Zeit erzeugt wird. k) als wir mit S (k) umgehen mussten. Aber B (k) ist immer noch kleiner als der vorherige "kleine Teil", S (k-1) und sobald wir B (k) verarbeiten, haben wir es vom Stapel genommen , Das ist also ein Punkt kleiner als wenn wir S (k) verarbeitet haben, und die gleiche Größe wie bei der Verarbeitung von S (k-1). Also haben wir immer noch unsere Grenze.
Nehmen wir an, wir machen es andersherum - schieben Sie den kleinen Teil und arbeiten Sie weiter mit dem großen Teil. Dann würden wir im pathologisch bösen Fall jedes Mal einen Bereich 1 auf den Stapel schieben und mit einer Größe arbeiten, die nur 2 kleiner als die vorherige Größe ist. Daher würden wir n / 2 Slots in unserem Stack benötigen.
Betrachten Sie den schlechtesten Fall, in dem Sie so partitionieren, dass Ihre Partition 1: n ist. Wenn Sie zuerst eine kleine Unterdatei sortieren, müssen Sie nur O (1) Leerzeichen verwenden, während Sie die große Unterdatei verschieben und dann wieder zurückgeben (und dann erneut die große Unterdatei drücken). Wenn Sie jedoch eine große Subdatei zuerst sortieren, benötigen Sie den O (N) -Raum, da Sie weiterhin ein Elementarray in den Stapel schieben.
Hier ist ein Zitat aus den Algorithmen von ROBERT SEDGEWICK (er war derjenige, der darüber geschrieben hat):
Für Quicksort die Kombination aus Endrekursionsentfernung und einer Richtlinie der Verarbeitung der kleineren der beiden Subdateien zuerst herausstellt stellen Sie sicher, dass der Stapel nur Platz für ungefähr, lg N Einträge enthalten muss, da jeder Eintrag auf dem Stapel nach dem obersten einen a darstellen muss Subdatei weniger als die Hälfte der Größe des vorherigen Eintrags.
OK, bin ich richtig, dass Sie meinen, wenn wir den Quicksort-Algorithmus nicht-rekursiv machen, müssen Sie einen Stapel verwenden, in dem Sie Partitionen auf den Stapel legen?
Wenn ja: Ein Algorithmus muss für jede Variable Speicher reservieren. Wenn Sie also zwei Instanzen parallel ausführen, weisen sie die doppelte Menge eines Algorithmusspeicherbereichs zu ...
Nun, in einer rekursiven Version, starten Sie eine neue Instanz des Algorithmus (der Speicher reservieren muss) ABER die Instanz, die die rekursive Instanz aufruft, endet NICHT, also wird der zugewiesene Speicher benötigt! - & gt; In der Tat haben wir begonnen, sagen wir 10 rekursive Instanzen und benötigen 10 * X Speicher, wobei X der Speicher ist, den eine Instanz benötigt.
Nun verwenden wir den nicht-rekursiven Algorithmus. Sie MÜSSEN nur den benötigten Speicher ONCE zuweisen. Tatsächlich verwenden Helfervariablen nur den Platz einer Instanz. Um die Funktion des Algorithmus zu erfüllen, müssen wir die bereits gemachten Partitionen speichern (oder was wir noch nicht gemacht haben). Tatsächlich legen wir es auf einen Stapel und nehmen die Partitionen ab, bis wir den letzten "Rekursionsschritt" gemacht haben. Stellen Sie sich vor: Sie geben dem Algorithmus ein Array. Der rekursive Algorithmus muss das ganze Array und einige Hilfsvariablen mit jeder Instanz zuweisen (wieder: wenn die Rekursionstiefe 10 ist, benötigen wir 10 × X Speicher, wo das Array viel benötigt). Der nicht-rekursive muss das Array, Hilfsvariablen nur einmal zuweisen, aber es braucht einen Stapel. Am Ende werden Sie jedoch nicht so viele Teile auf den Stack legen, dass der rekursive Algorithmus weniger Speicherplatz benötigt, weil wir das Array nicht jedes Mal neu zuordnen müssen.
Ich hoffe, ich habe es so beschrieben, dass Sie es verstehen können, aber mein Englisch ist nicht sooo gut. :)