Sortieralgorithmen, die einen zufälligen Komparator akzeptieren

https://cs.stackexchange.com/questions/2336

16-10-2019
|

Frage

Generische Sortieralgorithmen nehmen im Allgemeinen eine Reihe von Daten zur Sortierung und eine Komparatorfunktion, die zwei einzelne Elemente vergleichen kann. Wenn der Komparator eine Bestellbeziehung ist, ist die Ausgabe des Algorithmus eine sortierte Liste/ein Array.

Ich frage mich jedoch, welche Art Algorithmen tatsächlich tun würden Arbeit mit einem Vergleicher, der keine Ordnungsverhältnis ist (insbesondere eine, die bei jedem Vergleich ein zufälliges Ergebnis zurückgibt). Mit "Arbeit" meine ich hier, dass sie weiterhin eine Permutation ihrer Input zurückgeben und zu ihrer typisch zeitlichen Komplexität laufen (im Gegensatz zu dem schlimmsten Fall, das immer immer ein- oder in eine unendliche Schleife oder fehlende Elemente eingeht). Die Bestellung der Ergebnisse wäre jedoch undefiniert. Noch besser ist, dass die resultierende Bestellung eine einheitliche Verteilung ist, wenn der Komparator ein Münzflip ist.

Aus meiner groben mentalen Berechnung scheint eine Zusammenführungsart in Ordnung zu sein und die gleichen Laufzeitkosten beizubehalten und eine faire zufällige Bestellung zu erzeugen. Ich denke, dass so etwas wie eine schnelle Art degeneriert, möglicherweise nicht fertig sein und nicht fair sein würde.

Welche anderen Sortieralgorithmen (außer der Sortierung von Zusammenführungen) würden wie mit einem zufälligen Komparator beschrieben?

Als Referenz ist ein Komparator eine Ordnungsverhältnis, wenn es sich um eine ordnungsgemäße Funktion (deterministisch) handelt und die Axiome einer Ordnungsbeziehung erfüllt:
- Es ist deterministisch: compare(a,b) für eine bestimmte a und b Gibt 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

(Angenommen, alle Eingabelemente sind unterschiedlich, daher ist Reflexivität kein Problem.)

Ein zufälliger Komparator verstößt gegen alle diese Regeln. Es gibt jedoch Vergleiche, die keine Auftragsbeziehungen sind, aber nicht zufällig sind (zum Beispiel könnten sie möglicherweise nur eine Regel und nur für bestimmte Elemente im Satz verletzen).

Lösung

Grundsätzlich möchten Sie also wissen, ob es irgendwelche Sortieralgorithmus gibt, die sich nicht von seinem durchschnittlichen Fall abbauen würden, wenn eine Vergleichsfunktion ähnelt wie folgt:

int Compare(object a, object b) { return Random.Next(-1,1); }

... wobei random.next () eine Methode ist, die eine zufällig generierte Ganzzahl zwischen einer angegebenen inklusiven Unter- und Obergrenze erzeugt.

Die Antwort lautet tatsächlich, dass die grundlegendsten Sortieralgorithmen nach ihrem durchschnittlichen Fall abschneiden, da sie mindestens einer der folgenden zwei Bedingungen gehorchen:

Ein Vergleich zwischen zwei einzigartigen Elementen wird nie zweimal in der Art und/oder vorgenommen
In jeder Iteration der Art wird die korrekte Position von mindestens einem Element bestimmt und so dass das Element nie wieder verglichen wird.

Zum Beispiel findet SelectionsOrt durch die Unterliste ungeortlicher Elemente, findet das "kleinste" und/oder "größte" Element (indem sie jeden bisher mit dem größten vergleicht) in seine richtige Position und wiederholt es. Infolgedessen wird der Algorithmus auch bei einem nicht deterministischen Komparator am Ende jeder Iteration einen Wert gefunden, den er für am wenigsten oder am größten mit dem Element in der Position, die es zu bestimmen versucht, getauscht und niemals berücksichtigt wird, und berücksichtigt nie Dieses Element, sodass es die Bedingung 2. jedoch während dieses Prozesses mehrmals verglichen werden kann (als extremste Beispiel, betrachten Sie mehrere Selections -SORTS -Durchgänge in einem Array, das in umgekehrter Reihenfolge sortiert ist), sodass es gegen den Zustand 1 verstößt .

Mergesort folgt Bedingung 1, aber nicht 2; Da Sub-Arrays zusammengeführt werden, 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 untereinander in Ordnung sind; Der Algorithmus vergleicht nur das am wenigsten unmerdigende Element jedes Subtarrays mit dem anderen, um festzustellen, welches geringer ist und als nächstes in die zusammengeführte Liste gehen sollte. Dies bedeutet, dass zwei einzigartige Objekte A und B maximal einmal miteinander verglichen werden, aber der "endgültige" Index eines bestimmten Elements in der vollständigen Sammlung ist erst bekannt, wenn der Algorithmus abgeschlossen ist.

Insertionsort folgt nur Bedingung 1, obwohl seine Gesamtstrategie und Komplexität eher wie Selectionsort aussieht. Jedes ungewöhnliche Element wird mit sortierten Elementen, die größte First, verglichen werden, bis einer gefunden wird, der weniger als das untersuchende Element ist. Das Element wird an diesem Punkt eingefügt und dann wird das nächste Element 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 erst bekannt werden, wenn alle Elemente berücksichtigt werden.

Quicksort folgt beide Bedingungen. Auf jeder Ebene wird ein Drehpunkt ausgewählt und angeordnet, so dass die "linke" Seite Elemente enthält, die weniger als die Drehung und die "rechte" Seite enthält Elemente, die größer als der Drehung sind. Das Ergebnis dieser Ebene ist QuickSort (links) + Pivot + Quicksort (rechts), was im Grunde die Position des Drehzahlelements bedeutet (ein Index größer als die Länge der linken Seite), der Drehzahl wird niemals mit einem anderen Element verglichen Nachdem es als Drehpunkt ausgewählt wurde (es wurde möglicherweise mit früheren Pivot -Elementen verglichen, aber diese Elemente sind auch bekannt und sind in keiner Teil der Unterbarrays enthalten), und A und B, die auf den gegenüberliegenden Seiten des Drehes landen verglichen. In den meisten Implementierungen von Pure Quicksort ist der Basisfall ein Element, an dem sein aktueller Index sein endgültiger Index ist und keine weiteren Vergleiche durchgeführt werden.

Die einzige vergleichende Sorte, die ich mir vorstellen kann, würde einer der beiden Bedingungen nicht eingehalten werden, ist eine nicht optimierte Bubblesort. Wenn die Sortierung nicht akzeptiert, dass sich die X größten Elemente nach dem Ausführen von X-Pässen an ihrem richtigen Ort befinden, und/oder ein "Doppelprüfung" -Passe verwendet, um zu überprüfen, ob die Liste sortiert ist, wird die Sortierung nur als "fertig" angesehen, wenn die Der zufällige Komparator hat für jeweils zwei benachbarte Elemente in der Liste während eines Passs -1 oder 0 zurückgegeben, und daher wurden keine Swaps durchgeführt (ein Ereignis, das, wenn es wirklich zufällig ist, mit Wahrscheinlichkeit $ (2/3)^{n -1} auftreten würde $; für eine relativ kleine Liste von 25 Elementen, das ist eine Chance im Jahr 2000, während für 100 Elemente die Wahrscheinlichkeit 3,7*10 beträgt^-18). Mit zunehmender maximaler Absolutwert des Ergebnisses des Komparators nimmt die Wahrscheinlichkeit für einen Vergleich mit Rückkehr negativ oder Null in Richtung 0,5 ab, was die Chance macht, den Algorithmus zu beenden, so viel weniger wahrscheinlich (die Wahrscheinlichkeit von 99 Münzen flippt alle Landungsköpfe um Das ist im Grunde das, worauf dies läuft, 1 in 1,2*10 ist³⁰)

Lange später bearbeiten: Es gibt einige "Sorts", die speziell als Beispiele dafür entwickelt wurden, was nicht zu tun ist, was einen zufälligen Komparator enthält. Das vielleicht berühmteste ist Bogosort. "Wenn die Liste nicht in Ordnung ist, mischen Sie die Liste und überprüfen Sie erneut." Theoretisch wird es letztlich Treffer auf die richtige Permutation der Werte, genau wie der "nicht optimierte Bubblesort" oben, aber der durchschnittliche Fall ist faktorielles Zeit (n!/2) und aufgrund des Geburtstagsproblems (nach genügend zufälligen Permutationen werden Sie wahrscheinlicher, dass Sie wahrscheinlicher sind Begegnungen doppelte Permutationen als einzigartige) Es besteht eine Möglichkeit, dass der Algorithmus niemals zum offiziellen Abschluss des Algorithmus ist.

Andere Tipps

Jeder Algorithmus, der die gleichen zwei Elemente zweimal vergleicht Am häufigsten Sortieralgorithmen (Zusammenführen, Quicksort, Bubble-Sort, Insertion-Sort). Jeder Algorithmus, bei dem Elementpaare höchstens die gleichen (durchschnittlichen) Laufzeitkosten vergleicht, unabhängig vom Verhalten der Vergleichsfunktion. Wenn größere und weniger als sind ebenso wahrscheinlich die Ergebnisse. Andernfalls können Sie zumindest garantieren, dass der Sortieralgorithmus nicht schlechter ist als die Worst-Case-Laufzeit, die für jeden anständigen Sortieralgorithmus weniger als $ O (n^2) $ ist.

Ich glaube, eine interessantere Frage ist, wie Gut Ein solcher Algorithmus würde sich ausführen, wenn die Vergleichsfunktion beispielsweise 90% der Fälle durchschnittlich die richtige Antwort geben würde. Mit wie gut würde ich die Frage beantworten: "Was ist durchschnittlich die Anzahl der fehlgeleiteten Artikel beim Sortieren einer Liste von $ n $ durch diesen Algorithmus?"

Bearbeiten: Das Problem ist interessanter, als ich zum ersten Mal dachte. Hier ist ein weiterer Kommentar:

Angenommen, Ihre $ Compare $ function ist Messe, das heißt $ compare (x, y) = true $ mit Wahrscheinlichkeit $ 1/2 $ und $ false $ mit Wahrscheinlichkeit auch 1/2 $. Erinnern Sie sich an den Algorithmus zum Insertion -Sort (funktionaler Stil):

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

Die durchschnittliche Laufzeit dieses Algorithmen $ einfügen $ $ auf einer Liste von $ k $, wenn wir nur Anträge von $: $ als Kosten zählen (wenn wir auch Zerstörungen zählen, ist die Formel ähnlich).

Jetzt für $ vergleichen $ $ wie oben beschrieben ist dies recht klein: Die durchschnittliche Anzahl der durch das Einfügen ausgeführten Schritte ist angegeben durch:

$$ sum_ {i = 1}^{k} i 2^{-i} leq sum_ {i = 1}^{ infty} i 2^{-i} = 2 $$

Dies ergibt eine durchschnittliche Laufzeit von $ o (2n) $ für die Einfügungssorte, was deutlich besser ist als die durch eine "anständige" Vergleichsfunktion angegebene $ o (n^2) $.

Es würde Spaß machen, die durchschnittlichen Laufzeiten für die verschiedenen anderen Algorithmen mit dieser einheitlichen Vergleichsfunktion herauszufinden.

Mergesort mit einem fairen zufälligen Komparator ist nicht fair. Ich habe keinen Beweis, aber ich habe sehr starke empirische Beweise. (Faire bedeutet einheitlich verteilt.)

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs

Eine sehr verwandte Frage wird in beantwortet Alle möglichen Permutationen (funktionelle Perle) von Christiansen, Danilenko und Dylus. Sie führen einen Sortieralgorithmus in der Listen Sie Monad auf, die im Wesentlichen den Nichtdeterminismus simuliert und alle Permutationen einer bestimmten Eingabeliste zurückgeben. Die interessante Eigenschaft ist, dass jede Permutation genau einmal zurückgegeben wird.

Zitat aus der Zusammenfassung:

...

In diesem Artikel betrachten wir die Kombination aus Nichtdeterminismus und Sortierung in einem anderen Licht: Bei einer Sortierfunktion wenden wir sie auf ein nicht detministisches Prädikat an, um eine Funktion zu erhalten, die die Permutationen der Eingabeliste auflistet. Wir gehen die notwendigen Eigenschaften der Sortieralgorithmen und Prädikate im Spiel auf den Grund und diskutieren Variationen des modellierten Nichtdeterminismus.

Darüber hinaus formulieren und beweisen wir einen Theorem, der angibt, dass die entsprechende Permutationsfunktion unabhängig von der Sortierfunktion alle Permutationen der Eingabeliste aufzählt. Wir verwenden freie Theoreme, die allein aus der Art einer Funktion abgeleitet sind, um die Aussage zu beweisen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit cs.stackexchange