Sortieralgorithmen, die einen Zufallsvergleicher akzeptieren

22

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?


  1. 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 bestimmtes aund gibt bimmer 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 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).

edA-qa mort-ora-y
quelle
(1) Was meinst du damit, dass die Vergleichsfunktion stabil ist? (2) Sind "nicht stabil" und "zufällig" synonym?
Tsuyoshi Ito
"Laufen Sie mit ihrer üblicherweise angegebenen Zeitkomplexität (im Gegensatz zu einer Verschlechterung auf das Worst-Case-Szenario)." - Die üblicherweise angegebene Zeitkomplexität ist Worst-Case. "Die Reihenfolge wäre eine faire zufällige Reihenfolge." Gehen Sie davon aus, dass der Komparator auch einheitlich ist?
Raphael
Vielleicht nicht in der formalen Theorie, aber in der Praxis (Programmiersprachen) werden viele Dinge in amortisierter Zeit zitiert. Beispielsweise wird Quicksort häufig als angezeigt, aber tatsächlich als . O ( n 2 )O(logn)O(n2)
edA-qa mort-ora-y
4
@ edA-qamort-ora-y: (1) Sie meinen , nicht . (2) Das ist nicht das, was " abgeschriebene Zeit " bedeutet; Sie meinen " erwartete Zeit " oder weniger formal "typische Zeit". O ( log n )O(nlogn)O(logn)
JeffE
1
Niemand hat sich mit der (für mich) interessanteren Frage befasst, die oben gestellt wurde: Welche Sortieralgorithmen (falls vorhanden) haben die Eigenschaft, dass, wenn der Komparator ein Münzwurf ist, das Ergebnis eine einheitliche Permutation ist.
Joe

Antworten:

13

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:

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 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:

  1. Ein Vergleich zwischen zwei eindeutigen Elementen wird in der Sortierung und / oder nie zweimal durchgeführt
  2. In jeder Iteration dieser Art wird die korrekte Position von mindestens einem Element bestimmt, so dass dieses Element nie wieder verglichen wird.

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)N1). 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.

KeithS
quelle
Würde Bedingung 2 auch die schnelle Sortierung abdecken? Oder wäre es eher eine dritte Bedingung, wenn jede Iteration kleiner wäre als die letzte?
edA-qa mort-ora-y
QuickSort würde in meinen Augen von beiden Bedingungen abgedeckt sein. In effizienten QuickSorts wählen Sie den Pivot aus, vergleichen dann jedes Element mit ihm und tauschen Elemente aus, die sich auf der falschen "Seite" des Pivots befinden. Sobald die Elemente angeordnet sind, gibt die Funktion QuickSort (links) + Pivot + QuickSort (rechts) zurück und der Pivot wird nicht an niedrigere Ebenen weitergereicht. Also, beide Bedingungen sind wahr; Sie vergleichen ein eindeutiges a und b nie mehr als einmal und haben den Index des Pivots zu dem Zeitpunkt bestimmt, an dem Sie die anderen Elemente angeordnet haben.
KeithS
Tolle Antwort, aber ich stimme Ihnen in Bezug auf BubbleSort nicht zu. Bei Verwendung eines konsistenten Komparators weiß BubbleSort bei der i-ten Iteration, dass sich die letzten i-1-Elemente an ihrer endgültigen Stelle befinden, und jede sinnvolle Implementierung von BubbleSort durchläuft bei jeder Iteration weniger Elemente. Daher sollte BubbleSort auch nach n Iterationen angehalten werden .
Boris Trayvas
Nach einigem Nachdenken stimme ich Ihnen eher zu. nach X geht, sind die größten X - Werte in ihrem richtigen Platz, so dass Sie das Problem Raum bei jedem Durchlauf reduzieren und so wäre ein effizienter Algorithmus gehorchen Bedingung 2. Ich bearbeiten werde
Keiths
Bei der Implementierung von Quicksort müsste man vorsichtig sein. Es kann davon ausgegangen werden, dass die Suche nach einem Element, das nicht kleiner als der Drehpunkt ist, endet, wenn wir auf den Drehpunkt oder ein Element stoßen, das größer als der Drehpunkt ist. das wäre nicht unbedingt der Fall.
gnasher729
10

O(n2)

n


Edit: Das Problem ist interessanter, als ich zuerst dachte, also hier ist ein weiterer Kommentar:

comparecompare(x,y)=true1/2false1/2

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 []

k=1nf(k)nlf(k)ichnsertk:

cOmpeinre

ich=1kich2-ichich=1ich2-ich=2

O(2n)O(n2)

Bei dieser einheitlichen Vergleichsfunktion würde es Spaß machen, die durchschnittlichen Laufzeiten für die verschiedenen anderen Algorithmen zu ermitteln.

Cody
quelle
Quicksort kann Vergleiche wiederholen, wenn dasselbe Element mehr als einmal als Pivot ausgewählt wurde (es kann in der Liste mehrmals vorkommen).
Raphael
2
@Raphael: Meine Wortwahl war schlecht: Ich meinte wiederholte Vergleiche zwischen Vorkommen von Elementen, die in Quicksort nicht mehr als einmal vorkommen.
Cody
1
@ Gilles: Ich kann mich irren, glaube aber nicht, dass die Transitivität des Vergleichs für die Laufzeit der meisten Sortieralgorithmen entscheidend ist. Richtigkeit sicher, aber das war nicht der Gegenstand der Frage.
Cody
@ Gilles: Das OP fragt nicht nach tatsächlich sortierenden Algorithmen. Er fragt, was mit Standardsortieralgorithmen passiert, wenn alle Vergleiche durch Münzwürfe ersetzt werden. Die resultierenden Algorithmen sortieren nicht (außer mit geringer Wahrscheinlichkeit), aber sie sind immer noch gut definierte Algorithmen.
JeffE
@ Jeff Ich verstehe das jetzt. So habe ich die Frage anfangs nicht gelesen, aber angesichts der Kommentare des Fragestellers war das gemeint.
Gilles 'SO- hör auf böse zu sein'
2

Mergesort mit einem fairen Zufallsvergleich ist nicht fair. Ich habe keinen Beweis, aber ich habe SEHR starke empirische Beweise. (Fair bedeutet gleichmäßig 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
Thomas Eding
quelle
Ist Haskell oder Caml jetzt in Mode?
Yai0Phah
Ich habe keine Ahnung. Aber Haskell ist eine meiner Lieblingssprachen, deshalb habe ich das darin programmiert. Pattern Matching machte dies einfacher.
Thomas Eding
0

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:

...

In diesem Artikel untersuchen wir die Kombination von Nichtdeterminismus und Sortieren in einem anderen Licht: Wenn wir eine Sortierfunktion haben, wenden wir sie auf ein nichtdeterministisches Prädikat an, um eine Funktion zu erhalten, die Permutationen der Eingabeliste auflistet. Wir gehen den notwendigen Eigenschaften der Sortieralgorithmen und Prädikate auf den Grund und diskutieren Variationen des modellierten Nichtdeterminismus.

Darüber hinaus formulieren und beweisen wir einen Satz, der besagt, dass unabhängig von der verwendeten Sortierfunktion die entsprechende Permutationsfunktion alle Permutationen der Eingabeliste auflistet. Wir verwenden freie Theoreme, die allein vom Typ einer Funktion abgeleitet sind, um die Aussage zu beweisen.

Petr Pudlák
quelle