Generische Sortieralgorithmen verwenden im Allgemeinen einen Datensatz zum Sortieren und eine Komparatorfunktion, mit der zwei einzelne Elemente verglichen werden können. Wenn der Komparator eine Ordnungsrelation¹ ist, ist die Ausgabe des Algorithmus eine sortierte Liste / ein sortiertes Array.
Ich frage mich jedoch, welche Sortieralgorithmen tatsächlich mit einem Vergleicher funktionieren würden , der keine Ordnungsrelation ist (insbesondere einer, der bei jedem Vergleich ein zufälliges Ergebnis zurückgibt). Mit "Arbeit" meine ich hier, dass sie weiterhin eine Permutation ihrer Eingabe zurückgeben und mit ihrer normalerweise angegebenen Zeitkomplexität ablaufen (im Gegensatz dazu, dass sie sich immer auf den schlimmsten Fall verschlechtern oder in eine Endlosschleife geraten oder Elemente fehlen). Die Reihenfolge der Ergebnisse wäre jedoch undefiniert. Noch besser wäre die resultierende Reihenfolge eine gleichmäßige Verteilung, wenn der Komparator ein Münzwurf ist.
Aus meiner groben mentalen Berechnung geht hervor, dass eine Zusammenführungssorte in Ordnung wäre, die gleichen Laufzeitkosten aufrechterhalten und eine faire zufällige Reihenfolge erzeugen würde. Ich denke, dass so etwas wie eine schnelle Sorte jedoch degeneriert, möglicherweise nicht beendet und nicht fair wäre.
Welche anderen Sortieralgorithmen (außer der Zusammenführungssortierung) funktionieren wie bei einem Zufallsvergleich beschrieben?
Als Referenz ist ein Komparator eine Ordnungsrelation, wenn er eine ordnungsgemäße Funktion (deterministisch) ist und die Axiome einer Ordnungsrelation erfüllt:
- es ist deterministisch:
compare(a,b)
für ein bestimmtesa
und gibtb
immer das gleiche Ergebnis zurück. - es ist transitiv:
compare(a,b) and compare(b,c) implies compare( a,c )
- es ist antisymmetrisch
compare(a,b) and compare(b,a) implies a == b
- es ist deterministisch:
(Angenommen, alle Eingabeelemente sind unterschiedlich, sodass Reflexivität kein Problem darstellt.)
Ein Zufallsvergleich verstößt gegen alle diese Regeln. Es gibt jedoch Komparatoren, die noch keine zufälligen Ordnungsbeziehungen haben (zum Beispiel verstoßen sie möglicherweise nur gegen eine Regel und nur für bestimmte Elemente in der Menge).
quelle
Antworten:
Im Grunde möchten Sie wissen, ob es einen Sortieralgorithmus gibt, der sich nicht von seinem Durchschnittsfall verschlechtert, wenn eine Vergleichsfunktion wie die folgende gegeben wird:
... wobei Random.Next () eine Methode ist, die eine zufällig generierte Ganzzahl zwischen einer angegebenen inklusive Unter- und Obergrenze erzeugt.
Die Antwort ist tatsächlich, dass die meisten grundlegenden Sortieralgorithmen gemäß ihrem Durchschnittsfall ausgeführt werden, da sie mindestens eine der folgenden beiden Bedingungen erfüllen:
Zum Beispiel durchläuft SelectionSort die Unterliste der unsortierten Elemente, findet das "kleinste" und / oder "größte" Element (indem jedes mit dem bisher größten verglichen wird), platziert es an seiner korrekten Position und wiederholt es. Selbst mit einem nicht deterministischen Komparator hat der Algorithmus am Ende jeder Iteration einen Wert gefunden, den er für am wenigsten oder am größten hält, und tauscht ihn mit dem Element an der Position aus, die er zu bestimmen versucht, und berücksichtigt ihn nie Dieses Element entspricht erneut der Bedingung 2. Während dieses Vorgangs können A und B jedoch mehrmals verglichen werden (als extremstes Beispiel sollten Sie mehrere Durchläufe von SelectionSort für ein Array in umgekehrter Reihenfolge berücksichtigen), sodass die Bedingung 1 verletzt wird .
MergeSort befolgt Bedingung 1 aber nicht 2; Beim Zusammenführen von Unterarrays werden Elemente im selben Unterarray (auf der linken oder rechten Seite) nicht miteinander verglichen, da bereits festgestellt wurde, dass die Elemente auf dieser Seite des Arrays in der richtigen Reihenfolge zueinander sind. Der Algorithmus vergleicht nur das am wenigsten nicht zusammengeführte Element eines jeden Subarrays mit dem anderen, um festzustellen, welches Element kleiner ist und in der zusammengeführten Liste als nächstes aufgeführt werden soll. Dies bedeutet, dass zwei beliebige eindeutige Objekte A und B maximal einmal miteinander verglichen werden. Der "letzte" Index eines bestimmten Elements in der vollständigen Sammlung ist jedoch erst bekannt, wenn der Algorithmus vollständig ist.
InsertionSort erfüllt auch nur Bedingung 1, obwohl seine Gesamtstrategie und Komplexität eher SelectionSort ähnelt. Jedes unsortierte Element wird mit den sortierten Elementen (größte zuerst) verglichen, bis eines gefunden wird, das kleiner ist als das zu überprüfende Element. Das Element wird an dieser Stelle eingefügt, und das nächste Element wird berücksichtigt. Das Ergebnis ist, dass die relative Reihenfolge von A und B durch einen Vergleich bestimmt wird und weitere Vergleiche zwischen A und B niemals durchgeführt werden, aber die endgültige Position eines Elements kann nicht bekannt sein, bis alle Elemente berücksichtigt sind.
QuickSort befolgt beideBedingungen. Auf jeder Ebene wird ein Drehpunkt so ausgewählt und angeordnet, dass die "linke" Seite Elemente enthält, die kleiner als der Drehpunkt sind, und die "rechte" Seite Elemente enthält, die größer als der Drehpunkt sind. Das Ergebnis dieser Ebene ist QuickSort (links) + Pivot + QuickSort (rechts). Dies bedeutet, dass die Position des Pivot-Elements bekannt ist (ein Index größer als die Länge der linken Seite). Der Pivot wird niemals mit einem anderen Element verglichen nachdem es als Pivot ausgewählt wurde (es wurde möglicherweise mit früheren Pivot-Elementen verglichen, aber diese Elemente sind ebenfalls bekannt und nicht in Subarrays enthalten), und A und B, die auf gegenüberliegenden Seiten des Pivots enden, sind es niemals verglichen. In den meisten Implementierungen von Pure QuickSort ist der Basisfall ein Element. An diesem Punkt ist der aktuelle Index der endgültige Index und es werden keine weiteren Vergleiche durchgeführt.
Die einzige vergleichende Sorte, von der ich mir vorstellen kann, dass sie keiner der beiden Bedingungen entspricht, ist eine nicht optimierte BubbleSort. Wenn die Sortierung nicht akzeptiert, dass sich die X größten Elemente nach dem Ausführen von X-Übergängen an der richtigen Stelle befinden, und / oder einen "Double-Check" -Übergang verwendet, um zu überprüfen, ob die Liste sortiert ist, wird die Sortierung nur dann als "erledigt" betrachtet, wenn die Der Zufallsvergleicher hat während eines Durchlaufs -1 oder 0 für jeweils zwei benachbarte Elemente in der Liste zurückgegeben, und daher wurden keine Auslagerungen durchgeführt (ein Ereignis, das, wenn es wirklich zufällig wäre, mit Wahrscheinlichkeit auftreten würde ; Für eine relativ kleine Liste mit 25 Elementen ist dies eine Chance von 1: 2000, während für 100 Elemente die Wahrscheinlichkeit 3,7 * 10 -18 beträgt( 2 / 3 )N- 1 ). Wenn der maximale Absolutwert des Ergebnisses des Komparators steigt, sinkt die Wahrscheinlichkeit, dass ein Vergleich negativ oder null zurückgibt, in Richtung 0,5, wodurch die Chance, den Algorithmus zu beenden, sehr viel geringer ist (die Chance, dass 99 Münzen alle Landeköpfe umwerfen) , worauf es im Grunde ankommt, ist 1 in 1,2 * 10 30 )
SPÄTER LANG BEARBEITEN: Es gibt einige "Sortierungen", die speziell als Beispiele dafür gedacht sind, was nicht zu tun ist, und die einen Zufallsvergleich enthalten. Das vielleicht berühmteste ist BogoSort. Msgstr "Wenn eine Liste nicht in Ordnung ist, mische die Liste und überprüfe sie erneut". Theoretisch wird es irgendwann auf die richtige Permutation von Werten treffen, genau wie die "nicht optimierte BubbleSort" oben, aber der Durchschnittsfall ist Fakultätszeit (N! / 2) und wegen des Geburtstagsproblems (nach genügend zufälligen Permutationen) Es besteht eine ungleiche Wahrscheinlichkeit, dass der Algorithmus niemals offiziell abgeschlossen wird. Der Algorithmus ist zeitlich unbegrenzt.
quelle
Edit: Das Problem ist interessanter, als ich zuerst dachte, also hier ist ein weiterer Kommentar:
Bei dieser einheitlichen Vergleichsfunktion würde es Spaß machen, die durchschnittlichen Laufzeiten für die verschiedenen anderen Algorithmen zu ermitteln.
quelle
Mergesort mit einem fairen Zufallsvergleich ist nicht fair. Ich habe keinen Beweis, aber ich habe SEHR starke empirische Beweise. (Fair bedeutet gleichmäßig verteilt.)
quelle
Eine sehr ähnliche Frage wird in Alle Arten von Permutationen (Functional Pearl) von Christiansen, Danilenko und Dylus beantwortet. Sie führen einen Sortieralgorithmus in der Listenmonade aus , der im Wesentlichen den Nichtdeterminismus simuliert und alle Permutationen einer bestimmten Eingabeliste zurückgibt. Die interessante Eigenschaft ist, dass jede Permutation genau einmal zurückgegeben wird.
Zitat aus dem Abstract:
quelle