tl; dr: Ist es möglich, Quicksort auf einer doppelt verknüpften Liste effizient zu implementieren? Mein Verständnis, bevor ich darüber nachdachte, war, nein, es ist nicht.
Neulich hatte ich Gelegenheit, die Iteratoranforderungen für die grundlegenden Sortieralgorithmen zu berücksichtigen. Die grundlegenden O (N²) -Einheiten sind ziemlich einfach.
Quicksort
Der introsort_loop in std :: sort (wie in der GNU-Standardbibliothek / hp (1994) / silicon graphics (1996)) verlangt, dass es random_access ist.
%Vor%Wie ich es erwartet habe.
Jetzt kann ich bei näherer Betrachtung den wirklichen Grund nicht finden, dies für Quicksort zu verlangen. Das einzige, was explizit random_access_iterators erfordert, ist der Aufruf std::__median , der die Berechnung des mittleren Elements erfordert. Der reguläre Vanilla Quicksort berechnet nicht den Median.
Die Partitionierung besteht aus einem Check
%Vor%Nicht wirklich eine nützliche Überprüfung für Bidirektionale. Allerdings sollte man dies durch einen Check in der vorherigen Partitionierungsfahrt (von links nach rechts / rechts nach links) mit einer einfachen Bedingung von
ersetzen können %Vor%Ist es möglich, Quicksort mit nur bidirektionalen Iteratoren relativ effizient zu implementieren? Die rekursive Tiefe kann immer noch geschützt werden.
NB. Ich habe noch keine tatsächliche Implementierung versucht.
tl; dr: Ja
Wie Sie sagen, besteht das Problem darin, das Pivot-Element zu finden, welches das Element in der Mitte ist. Wenn man dies mit einem wahlfreien Zugriff findet, nimmt O (1), bei bidirektionalen Iteratoren O (n) (n / 2 Operationen) , um genau zu sein). In jedem Schritt müssen Sie jedoch Subcontainer erstellen, wobei die linke und die rechte jeweils kleinere und größere Zahlen enthalten. Hier findet die Hauptarbeit der schnellen Sortierung statt, oder?
Beim Erstellen der Untercontainer (für den Rekursionsschritt) würde ich nun einen Iterator h erstellen, der auf ihr jeweiliges Frontelement zeigt. Wenn Sie nun ein nächstes Element auswählen, um zum Subcontainer zu wechseln, müssen Sie einfach h jedes zweite Mal vorrücken. Dies bedeutet, dass h auf das Pivot-Element zeigt, sobald Sie bereit sind, den neuen Rekursionsschritt zu durchlaufen.
Sie müssen nur den ersten Pivot finden, der eigentlich keine Rolle spielt, denn O (n log n + n / 2) = O (n log n).
Eigentlich ist dies nur eine Laufzeitoptimierung, hat aber keinen Einfluss auf die Komplexität, ob Sie einmal über die Liste iterieren (um jeden Wert in den entsprechenden Subcontainer zu setzen) oder zweimal (um den Pivot zu finden und dann jeden Wert zu setzen im jeweiligen Untercontainer) ist alles gleich: O (2n) = O (n).
Es ist einfach eine Frage der Ausführungszeit (nicht der Komplexität).
Sie benötigen Iteratoren mit wahlfreiem Zugriff, weil Sie das Pivot-Element in der Regel aus der Mitte der Liste auswählen möchten. Wenn Sie stattdessen das erste oder letzte Element als Pivot auswählen, reichen bidirektionale Iteratoren aus, aber dann degeneriert Quicksort für vorsortierte Listen zu O (n ^ 2).
Es gibt absolut kein Problem bei der Implementierung der Schnellsortierungsstrategie auf einer doppelt verknüpften Liste. (Ich denke, es kann auch leicht an eine einfach verknüpfte Liste angepasst werden). Die einzige Stelle in dem herkömmlichen Schnellsortieralgorithmus, die von der Random-Access-Anforderung abhängt, ist die Setup-Phase, die etwas "Schwieriges" verwendet, um das Pivot-Element auszuwählen. In Wirklichkeit sind all diese "Tricks" nichts anderes als nur Heuristiken, die durch ähnlich wirksame sequenzielle Methoden ersetzt werden können.
Ich habe die Quick-Sortierung für verknüpfte Listen zuvor implementiert. Es gibt nichts besonderes, man muss nur genau auf das richtige Element achten. Wie Sie wahrscheinlich verstehen, besteht ein großer Teil des Werts von Listensortieralgorithmen aus der Tatsache, dass Sie Elemente durch relinking statt durch explizites Wert-Swapping neu anordnen können. Nicht nur könnte es schneller sein, es auch (und oft - noch wichtiger) bewahrt die Wert-Gültigkeit von externen Referenzen, die an die Elemente der Liste angehängt werden können.
P.S. Ich würde jedoch sagen, dass der Merge-Sort-Algorithmus für verkettete Listen zu einer wesentlich eleganteren Implementierung führt, die eine ebenso gute Leistung bietet (es sei denn, Sie befassen sich mit einigen Fällen, die mit Quick-Sort besser abschneiden).
Tags und Links algorithm c++ quicksort stl-algorithm