Algorytmy sortowania, które akceptują losowy komparator

Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica.

Zastanawiam się jednak, które algorytmy sortowania faktycznie działałyby z komparatorem, który nie jest relacją rzędu (w szczególności, który zwraca losowy wynik przy każdym porównaniu). Przez „pracę” rozumiem tutaj, że nadal zwracają permutację swoich danych wejściowych i działają w typowo cytowanej złożoności czasowej (w przeciwieństwie do zawsze poniżania do najgorszego scenariusza, przechodzenia w nieskończoną pętlę lub brakujących elementów). Kolejność wyników byłaby jednak nieokreślona. Co więcej, wynikowe uporządkowanie byłoby równomiernym rozkładem, gdy komparator był monetą.

Z moich wstępnych kalkulacji mentalnych wynika, że ​​scalenie byłoby w tym dobre i utrzymywałoby ten sam koszt w czasie wykonywania i zapewniało uczciwe losowe porządkowanie. Myślę, że coś w rodzaju szybkiego rodzaju zdegenerowałoby się, być może nie skończyłoby się i nie byłoby uczciwe.

Jakie inne algorytmy sortowania (inne niż scalanie) działałyby tak, jak opisano w przypadku komparatora losowego?

1. Dla porównania, komparator jest relacją rzędu, jeśli jest właściwą funkcją (deterministyczną) i spełnia aksjomaty relacji rzędu:

   • jest deterministyczny: compare(a,b)dla określonego ai bzawsze zwraca ten sam wynik.
   • jest przechodnie: compare(a,b) and compare(b,c) implies compare( a,c )
   • jest antysymetryczny compare(a,b) and compare(b,a) implies a == b

(Załóżmy, że wszystkie elementy wejściowe są różne, więc zwrotność nie stanowi problemu).

Losowy komparator narusza wszystkie te zasady. Istnieją jednak komparatory, które nie są relacjami porządku, ale nie są losowe (na przykład mogą naruszać być może tylko jedną regułę i tylko dla określonych elementów w zestawie).

Zasadniczo chcesz wiedzieć, czy istnieje algorytm sortowania, który nie obniżyłby się w porównaniu ze średnim przypadkiem, gdyby podano funkcję porównania podobną do:

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

... gdzie Random.Next () to metoda, która wygeneruje losowo wygenerowaną liczbę całkowitą między określoną dolną i górną granicą włącznie.

Odpowiedź jest taka, że ​​większość podstawowych algorytmów sortowania będzie działać zgodnie z ich średnią wielkością, ponieważ spełniają co najmniej jeden z następujących dwóch warunków:

1. Porównanie dwóch unikalnych elementów nigdy nie jest wykonywane dwukrotnie w tym samym sortowaniu i / lub
2. W każdej iteracji tego rodzaju ustalana jest poprawna pozycja co najmniej jednego elementu, dzięki czemu element nigdy nie jest ponownie porównywany.

Na przykład SelectionSort dokonuje iteracji przez podlistę nieposortowanych elementów, znajduje element „najmniejszy” i / lub „największy” (przez porównanie każdego z największych jak dotąd), umieszcza go we właściwej pozycji i powtarza. W rezultacie, nawet przy niedeterministycznym komparatorze, pod koniec każdej iteracji algorytm znajdzie wartość, którą uważa za najmniejszą lub największą, zamienia ją na element w pozycji, którą próbuje określić i nigdy nie bierze pod uwagę ten element ponownie, dlatego spełnia warunek 2. Jednak A i B mogą być wielokrotnie porównywane podczas tego procesu (jako najbardziej ekstremalny przykład rozważ kilka przejść SelectionSort na tablicy posortowanej w odwrotnej kolejności), więc narusza warunek 1 .

MergeSort spełnia warunek 1, ale nie 2; w miarę łączenia się pod-macierzy elementy w tej samej pod-macierzy (po lewej lub po prawej stronie) nie są porównywane ze sobą, ponieważ już ustalono, że elementy po tej stronie tablicy są między sobą w porządku; algorytm porównuje tylko najmniej niezablokowany element każdej podtablicy z drugą, aby ustalić, która jest mniejsza i powinna przejść dalej na scalonej liście. Oznacza to, że dowolne dwa unikalne obiekty A i B zostaną porównane maksymalnie jeden raz, ale „ostateczny” indeks danego elementu w pełnej kolekcji nie jest znany, dopóki algorytm nie zostanie ukończony.

InsertionSort spełnia również tylko Warunek 1, mimo że jego ogólna strategia i złożoność bardziej przypomina SelectionSort. Każdy nieposortowany element jest porównywany z posortowanymi elementami, poczynając od największego, aż do znalezienia jednego mniejszego niż badany element. element jest wstawiany w tym punkcie, a następnie rozważany jest następny element. Rezultat jest taki, że względna kolejność dowolnego A i B jest określona przez jedno porównanie, a dalsze porównania między tym A i B nigdy nie są wykonywane, ale końcowa pozycja dowolnego elementu nie może być znana, dopóki wszystkie elementy nie zostaną uwzględnione.

QuickSort przestrzega obu tych zasadWarunki. Na każdym poziomie wybiera się i ustawia czop w taki sposób, że „lewa” strona zawiera elementy mniejsze niż czop, a „prawa” strona zawiera elementy większe niż czop. Wynikiem tego poziomu jest QuickSort (lewy) + pivot + QuickSort (prawy), co w zasadzie oznacza, że ​​pozycja elementu przestawnego jest znana (jeden indeks większy niż długość lewej strony), oś nigdy nie jest porównywana z żadnym innym elementem po wybraniu go jako elementu przestawnego (można go porównać z poprzednimi elementami elementu przestawnego, ale elementy te są również znane i nie są zawarte w żadnych podgrupach) ORAZ wszelkie elementy A i B, które kończą się po przeciwnych stronach elementu przestawnego, nigdy nie są w porównaniu W większości implementacji czystego QuickSort, przypadek podstawowy jest jednym elementem, w którym to momencie jego bieżący indeks jest indeksem końcowym i nie dokonuje się dalszych porównań.

Jedyny rodzaj porównawczy, jaki mogę wymyślić, który nie spełniałby żadnego z tych warunków, to niezoptymalizowany BubbleSort. Jeśli sortowanie nie zaakceptuje, że X największych elementów jest na swoim właściwym miejscu po uruchomieniu pasaży X i / lub użyje przepustki „podwójnego sprawdzania”, aby sprawdzić, czy lista jest posortowana, sortowanie zostanie uznane za „wykonane”, gdy losowo komparator powrócił 1 lub 0 do każdych dwóch sąsiednich elementów listy podczas przechodzenia, a zatem nie swapy wykonywanych (zdarzenia, które, jeśli w pełni losowe, mogłoby nastąpić z prawdopodobieństwem , dla stosunkowo mała lista 25 elementów, to szansa na jeden w 2000 roku, podczas gdy dla 100 elementów prawdopodobieństwo wynosi 3,7 * 10 ^-18$(2/3)^{N-1}$). W miarę wzrostu maksymalnej wartości bezwzględnej wyniku komparatora prawdopodobieństwo, że jedno porównanie zwróci wartość ujemną lub zero, zmniejsza się w kierunku .5, co sprawia, że ​​prawdopodobieństwo zakończenia algorytmu jest znacznie mniej prawdopodobne (szansa 99 monet przewraca wszystkie głowice lądujące , co w zasadzie sprowadza się do tego, wynosi 1 na 1,2 * 10 ³⁰ )

EDYCJA DŁUGIEGO PÓŹNIEJ: Istnieje kilka „rodzajów” zaprojektowanych specjalnie jako przykłady tego, czego nie należy robić, i które zawierają losowy komparator; być może najbardziej znanym jest BogoSort. „Biorąc pod uwagę listę, jeśli lista nie jest w porządku, przetasuj listę i sprawdź ponownie”. Teoretycznie ostatecznie trafi na właściwą permutację wartości, podobnie jak powyżej „niezoptymalizowany BubbleSort”, ale przeciętny przypadek to czas czynnikowy (N! / 2), a także z powodu problemu urodzinowego (po wystarczającej liczbie losowych permutacji ty bardziej prawdopodobne jest, że napotkamy duplikaty permutacji niż unikatowe) istnieje niezerowa możliwość, że algorytm nigdy się nie zakończy, aby oficjalnie algorytm nie był związany z czasem.

$O(n^2)$

$n$

Edycja: Problem jest bardziej interesujący, jak na początku myślałem, więc oto kolejny komentarz:

$compare$$compare(x,y)=true$$1/2$$false$$1/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 []

$\sum_{k=1}^{n} f(k)$$n$$l$$f(k)$$insert$$k$$:$

$compare$

$O(2n)$$O(n^2)$

Byłoby fajnie obliczyć średni czas działania dla różnych innych algorytmów, biorąc pod uwagę tę jednolitą funkcję porównywania.

Połączenie z uczciwym przypadkowym komparatorem nie jest sprawiedliwe. Nie mam dowodu, ale mam BARDZO mocne dowody empiryczne. (Sprawiedliwy oznacza równomiernie rozłożone).

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

Na bardzo podobne pytanie odpowiedzieli Christiansen, Danilenko i Dylus we Wszystkich rodzajach permutacji (Perła funkcjonalna) . Uruchamiają algorytm sortowania w monadzie listy , który zasadniczo symuluje niedeterminizm, zwracając wszystkie permutacje z danej listy danych wejściowych. Ciekawą właściwością jest to, że każda permutacja jest zwracana dokładnie raz.

Cytowanie z streszczenia:

...

W tym artykule przyglądamy się kombinacji niedeterminizmu i sortowania w innym świetle: biorąc pod uwagę funkcję sortowania, stosujemy ją do niedeterministycznego predykatu w celu uzyskania funkcji, która wylicza permutacje listy wejściowej. Dochodzimy do sedna niezbędnych właściwości algorytmów sortowania i predykatów w grze, a także omawiamy warianty modelowanego niedeterminizmu.

Ponadto formułujemy i potwierdzamy twierdzenie, że bez względu na to, jakiej funkcji sortowania używamy, odpowiednia funkcja permutacji wylicza wszystkie permutacje listy wejściowej. Używamy wolnych twierdzeń, które wywodzą się z samego rodzaju funkcji, aby udowodnić to twierdzenie.