Gibt es einen Sortieralgorithmus, der bei Verwendung eines Münzwurfkomparators eine zufällige Permutation zurückgibt?

Inspiriert von dieser Frage, bei der der Fragesteller wissen möchte, ob sich die Laufzeit ändert, wenn der in einem Standardsuchalgorithmus verwendete Komparator durch einen fairen Münzwurf ersetzt wird, und auch von Microsofts prominentem Versagen, einen einheitlichen Permutationsgenerator zu schreiben, ist meine Frage daher ::

Gibt es einen vergleichsbasierten Sortieralgorithmus, der abhängig von unserer Implementierung des Komparators:

1. Geben Sie die Elemente in sortierter Reihenfolge zurück, wenn Sie einen echten Komparator verwenden (dh der Vergleich macht das, was wir von einem Standardsortieralgorithmus erwarten).
2. Geben Sie eine gleichmäßig zufällige Permutation der Elemente zurück, wenn der Komparator durch einen fairen Münzwurf ersetzt wird (dh geben Sie x < y = truemit der Wahrscheinlichkeit 1/2 zurück, unabhängig vom Wert von x und y).

Der Code für den Sortieralgorithmus muss identisch sein. Nur der Code in der Vergleichsbox "Black Box" darf sich ändern.

Der folgende deterministische Algorithmus (ohne Komparator) funktioniert für ein Eingabetupel :$(a_1,\dots,a_n)$

1. Führen Sie den Fisher-Yates-Shuffle mit Ihrem Komparator mit einem statischen Paar (z. B. ) als Münzwurf durch (Abtastung von Akzeptanz und Ablehnung). Wenn der Komparator das erste Mal ausgibt , verwenden Sie ihn invertiert, um im deterministischen Fall eine endlose Zurückweisungsschleife zu vermeiden.$a_1 < a_2$$1$
2. (Optionale Beschleunigung: Versuchen Sie ein einzelnes Paar mal, wobei die Länge oder Ihre Eingabe ist. Wenn sich zwei der Ausgaben unterscheiden, geben Sie die in (1) erhaltene Permutation zurück.)$n$$n$
3. Sortieren Sie Ihr Array mithilfe der Zusammenführungssortierung.

Bei einer deterministischen Ordnungsbeziehung als Komparator sortiert dieser Algorithmus ein Array in der Zeit da die Fisher-Yates-Zufallswiedergabe in Verwendung von maximal Nicht zufällige "Zufallsbits" (z. B. Aufrufe Ihres Komparators) in jedem Schritt und Zusammenführungssortierung haben dieselbe asymptotische Komplexität. Das Ergebnis von (1) ist in diesem Fall völlig nutzlos, aber da es von einer echten Art gefolgt wird, schadet dies nicht.O ( n ) O ( log n $\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

Wenn ein echter Münzwurf als Komparator (1) das Array mit gleicher Wahrscheinlichkeit für jede Permutation permutiert und wenn Sie wirklich (3) tun müssen (Sie haben (2) oder (2) ausgelassen, um die Zufälligkeit nicht zu bestimmen), ist dies nein Schaden, weil die Verteilung seines Ergebnisses nur von der Reihenfolge seiner Eingabe abhängt, die aufgrund von (1) gleichmäßig auf alle Permutationen verteilt ist, so dass auch das Ergebnis des gesamten Algorithmus gleichmäßig verteilt ist. Die Häufigkeit, mit der jede Akzeptanz-Zurückweisungs-Abtastung wiederholt werden muss, ist geometrisch verteilt (Zurückweisung mit der Wahrscheinlichkeit ) und hat daher einen erwarteten Wert . Jede Wiederholung verwendet höchstens Bits, sodass die Laufzeitanalyse fast dieselbe ist wie im deterministischen Fall, aber wir erhalten nur eine <2lognO(nlogn$< \frac{1}{2}$$< 2$$\log n$erwartete Laufzeit von mit der Möglichkeit der Nichtbeendigung (endet nur fast sicher ).$\mathcal{O}(n \log n)$

---

Wie Joe betonte: Wenn Ihnen der Test für das erste Bit in (1) nicht gefällt, machen Sie (3) und dann (1) und verwenden Sie das immer , da das Array im deterministischen Fall bereits sortiert ist . Zusätzlich müssen Sie Ihre Zufallszahl von der Obergrenze des Bereichs in der Schleife subtrahieren, da die Obergrenze für die Zufallszahl die identische Permutation ergibt. Beachten Sie jedoch, dass (2) dann verboten ist, da Sie im Lösegeldfall immer mischen müssen.$a_n < a_1$$0$

---

Sie können für (1) und (3) sogar dieselben Aufrufe an Ihren Komparator verwenden, aber dann zu beweisen, dass das Ergebnis gleichmäßig verteilt ist, ist zumindest viel schwieriger, wenn überhaupt möglich.

---

Der folgende Algorithmus hat keine unterschiedlichen Phasen zum Mischen und Sortieren, ist jedoch asymptotisch langsamer. Es handelt sich im Wesentlichen um eine Einfügesortierung mit binärer Suche . Ich werde , um die Eingabe zu bezeichnen, und , um das Ergebnis nach der ten Runde zu bezeichnen:$a=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Setze$b_{1,1} = a_1$
2. Wenn dann ist und sonst und . In beiden Fällen ist für einen nicht zufälligen Komparator immer (dh falsch).$a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$$a_d < a_c$$0$
3. Um für erhalten, erhalten Sie zuerst .$b_{k}$$k \geq 3$$b_{k-1}$
4. Sei und , dh ist die kleinste Potenz von nicht kleiner als .$l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
5. Sei . Für jedes lasse $i_0 = 0$$j \in \{1,\dots,l\}$ $$i_j = \begin{cases} i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} > k-1 \wedge a_d < a_c\\ i_{j-1} & i_{j-1} + 2^{l-j} > k-1 \wedge \neg (a_d < a_c)\\ i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} \leq k-1 \wedge b_{k-1,i_{j-1} + 2^{l-j}} < a_k \\ i_{j-1} & i_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b_{k-1,i_{j-1} + 2^{l-j}} < a_k) \\ \end{cases}$$
6. Wenn (5.) wiederholen, sonstb k = ( b k - 1 , 1 , ... , b k - 1 , i l - 1 , a k , b k - 1 , i l , ... , b k - 1 , k - 1$i_l > k$$b_k=(b_{k-1,1},\dots,b_{k-1,i_l -1},a_k,b_{k-1,i_l},\dots,b_{k-1,k-1})$
7. Ausgabe$b_n$

Zufälliger Fall: 5 + Die if-Klausel von 6 ist im Wesentlichen eine Akzeptanz-Ablehnungs-Stichprobe. Der Rest des Algorithmus ist ein naives Mischen: Mischen Sie die ersten Elemente und fügen Sie das te Element mit gleicher Wahrscheinlichkeit zu jeder Position hinzu. Wenn wir die normale Einfügungssortierung verwenden würden, würden wir stattdessen eine Binomialverteilung erhalten.$k-1$$k$

Beachten Sie, dass dieser Algorithmus in beiden Modi im Vergleich zum Fisher-Yates-Shuffle- und Merge-Sortieren ineffizient ist, da das Einfügen eines Elements an eine beliebige Position teuer ist, wenn ein Array verwendet wird und die binäre Suche bei Verwendung einer Liste lineare Zeit benötigt. Aber vielleicht könnte eine Modifikation der Heap-Sortierung oder der Baumsortierung auf ähnliche Weise zu einem schnelleren Algorithmus führen.

Nein, dies ist nur möglich, wenn . Die Wahrscheinlichkeit, dass eine Permutation von Ihrem Algorithmus unter Verwendung eines Zufallskomparators erzeugt wird, ist dyadisch, dh von der Form , während die Wahrscheinlichkeit betragen sollte. Wenn , gibt es keine Möglichkeit, zu schreibenin der Form .A / 2 B 1 / n ! n > 2 1 / n ! A / 2 $n \leq 2$$A/2^B$$1/n!$$n > 2$$1/n!$$A/2^B$