Ich lese das Buch Algorithmen in Kürze von O'Reilly Media und ich las gerade den Abschnitt über Sortieralgorithmen und fand einen, Median Sort 'genannt. Da ich noch nie zuvor davon gehört hatte und mein Lehrbuch von CS3 (welches Algorithmen umfasste) es nicht aufgelistet hatte, googelte ich es und versuchte, es auf Wikipedia nachzuschlagen und fand nichts. Ich würde es sehr schätzen, wenn jemand den Namen angeben könnte, könnte ich leicht den Algorithmus nach oben schauen oder mich auf andere Ressourcen darüber hinweisen. Danke.
Auch was ich über den Algorithmus sagen kann, ist im Wesentlichen Quicksort, außer dass immer der Medianwert als Pivot verwendet wird. Mit Medianwert meine ich, es scheint das Array von Elementen zu scannen und den mittleren Wert als Pivot auszuwählen, nicht das mittlere Element im Array als Pivot auszuwählen. Außerdem erwähnt das Buch einen Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) in Bezug auf die "Median" -Sorte.
Die meisten Versionen von Quicksort wählen (zum Beispiel) den Median von drei Elementen (typischerweise der erste, mittlere und letzte), was einen Mittelwert von 3 Quicksort ergibt. Nur mit dem mittleren Element als Pivot zu beginnen, ist normalerweise kein anderer Name als Quicksort.
Bearbeiten ( viel später, nachdem Sie die Änderung in der Frage gesehen haben): Es scheint, dass Sie mit dem Algorithmus "Median der Medianwerte" das Pivot-Element für einen QuickSort auswählen . Der Median des Median-Algorithmus ist besser dafür bekannt, unabhängig als Alternative zu (oder Verfeinerung von, abhängig von Ihrem Standpunkt) Hoares Select-Algorithmus verwendet zu werden. Dies ist bekannt, den Median (oder einen anderen Rang, aber in diesem Fall interessieren wir nur über Median) in linearer Zeit.
Die Quintessenz ist, dass die Sortierung wirklich immer noch ein Quicksort ist. Hoares Beschreibung der Wahl des Pivot-Elements erfordert weder, noch verbietet es ein Medium der Medianauswahl:
Der erste Schritt des Partitionierungsprozesses besteht darin, einen bestimmten Schlüsselwert auszuwählen, von dem bekannt ist, dass er innerhalb des Bereichs der Schlüssel der Elemente in dem Segment liegt, das sortiert werden soll. Eine einfache Methode, dies sicherzustellen, besteht darin, den tatsächlichen Schlüsselwert eines der Elemente im Segment auszuwählen. Der ausgewählte Schlüsselwert wird als gebunden bezeichnet.
Natürlich nennen fast alle es jetzt den "Pivot" anstelle der "Grenze", aber das ist meistens irrelevant. Die Methode zur Auswahl des Pivot / Bounds bleibt offen.
Ja, Sie haben Recht, es ist ähnlich wie Quicksort, aber es ist besser als Quicksort in der Art, dass es die Fälle vermeidet, in denen Ihre Arrays sehr disporporately (nicht in gleichen Hälften) unterteilt sind. Weil wir in quicksort nicht sicher sein können, dass unser Array jedes Mal in zwei gleiche Hälften oder nahezu gleiche Hälften geteilt wird. Bei der Median-Sortierung sichern wir dies, indem wir den Preis für die Suche nach dem Median zahlen Vorteile des Sortierens an Ort und Stelle.
Die meisten Versionen von Quicksort wählen (zum Beispiel) den Median von drei Elementen (typischerweise der erste, mittlere und letzte), was einen Mittelwert von 3 Quicksort ergibt. Nur mit dem mittleren Element als Pivot zu beginnen, ist normalerweise kein anderer Name als Quicksort.
Bearbeiten ( viel später, nachdem Sie die Änderung in der Frage gesehen haben): Es scheint, dass Sie mit dem Algorithmus "Median der Medianwerte" das Pivot-Element für einen QuickSort auswählen . Der Median des Median-Algorithmus ist besser dafür bekannt, unabhängig als Alternative zu (oder Verfeinerung von, abhängig von Ihrem Standpunkt) Hoares Select-Algorithmus verwendet zu werden. Dies ist bekannt, den Median (oder einen anderen Rang, aber in diesem Fall interessieren wir nur über Median) in linearer Zeit.
Die Quintessenz ist, dass die Sortierung wirklich immer noch ein Quicksort ist. Hoares Beschreibung der Wahl des Pivot-Elements erfordert weder, noch verbietet es ein Medium der Medianauswahl:
Der erste Schritt des Partitionierungsprozesses besteht darin, einen bestimmten Schlüsselwert auszuwählen, von dem bekannt ist, dass er innerhalb des Bereichs der Schlüssel der Elemente in dem Segment liegt, das sortiert werden soll. Eine einfache Methode, dies sicherzustellen, besteht darin, den tatsächlichen Schlüsselwert eines der Elemente im Segment auszuwählen. Der ausgewählte Schlüsselwert wird als gebunden bezeichnet.
Natürlich nennen fast alle es jetzt den "Pivot" anstelle der "Grenze", aber das ist meistens irrelevant. Die Methode zur Auswahl des Pivot / Bounds bleibt offen.
Ich lese das Buch Algorithmen in Kürze von O'Reilly Media und ich las gerade den Abschnitt über Sortieralgorithmen und fand einen, Median Sort 'genannt. Da ich noch nie zuvor davon gehört hatte und mein Lehrbuch von CS3 (welches Algorithmen umfasste) es nicht aufgelistet hatte, googelte ich es und versuchte, es auf Wikipedia nachzuschlagen und fand nichts. Ich würde es sehr schätzen, wenn jemand den Namen angeben könnte, könnte ich leicht den Algorithmus nach oben schauen oder mich auf andere Ressourcen darüber hinweisen. Danke.
Auch was ich über den Algorithmus sagen kann, ist im Wesentlichen Quicksort, außer dass immer der Medianwert als Pivot verwendet wird. Mit Medianwert meine ich, es scheint das Array von Elementen zu scannen und den mittleren Wert als Pivot auszuwählen, nicht das mittlere Element im Array als Pivot auszuwählen. Außerdem erwähnt das Buch einen Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) in Bezug auf die "Median" -Sorte.
Ich besitze das Buch nicht, aber ich werde es erraten. Der Algorithmus, auf den sich das Buch bezieht, ist der Floyd-Rivest SELECT -Algorithmus. Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) bezieht sich auf dieses Papier, in dem sie ihren früheren Auswahlalgorithmus PICK (jetzt bekannt als Median der Mediane ) diskutieren:
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, "Zeitgrenzen für die Auswahl", Journ. Komp. und. Sys. Sci., Vol. 7, iss. 4, S. 448-461, 1973.
In diesem Artikel wird das frühzeitige Verständnis des Auswahlproblems in der Informatik begründet.
Da ich das oben erwähnte Buch nicht besitze, nehme ich eine wilde Vermutung und sage das Blum-Floyd-Pratt-Rivest -Tarjan-Algorithmus (siehe auch das Papier , wenn Sie mehr darüber erfahren möchten) wahrscheinlich für die Pivot-Auswahl verwendet. Ich empfehle Ihnen auch, den Abschnitt Partition-basierte allgemeine Auswahlalgorithmus aus dem gleichen Wikipedia-Artikel zu lesen, da ich denke, dass es genau das ist, wonach Sie suchen.
Ja, Sie haben Recht, es ist ähnlich wie Quicksort, aber es ist besser als Quicksort in der Art, dass es die Fälle vermeidet, in denen Ihre Arrays sehr disporporately (nicht in gleichen Hälften) unterteilt sind. Weil wir in quicksort nicht sicher sein können, dass unser Array jedes Mal in zwei gleiche Hälften oder nahezu gleiche Hälften geteilt wird. Bei der Median-Sortierung sichern wir dies, indem wir den Preis für die Suche nach dem Median zahlen Vorteile des Sortierens an Ort und Stelle.
Ich besitze das Buch nicht, aber ich werde es erraten. Der Algorithmus, auf den sich das Buch bezieht, ist der Floyd-Rivest SELECT -Algorithmus. Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) bezieht sich auf dieses Papier, in dem sie ihren früheren Auswahlalgorithmus PICK (jetzt bekannt als Median der Mediane ) diskutieren:
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, "Zeitgrenzen für die Auswahl", Journ. Komp. und. Sys. Sci., Vol. 7, iss. 4, S. 448-461, 1973.
In diesem Artikel wird das frühzeitige Verständnis des Auswahlproblems in der Informatik begründet.