Algorytmy sortowania, które akceptują losowy komparator

22

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?

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

algorithms randomized-algorithms sorting

— edA-qa mort-ora-y
źródło

(1) Co rozumiesz przez to, że funkcja porównywania jest stabilna? (2) Czy „niestabilny” i „losowy” jest synonimem?

— Tsuyoshi Ito

„biegnij z ich typowo złożonym czasem (w przeciwieństwie do poniżania do najgorszego scenariusza” - zazwyczaj cytowany złożoność czasu jest najgorszym przypadkiem! ”porządkowanie byłoby uczciwym przypadkowym porządkowaniem” - BY „sprawiedliwy” masz na myśli mundur? Czy zakładasz, że komparator też jest jednolity?

— Raphael

Być może nie w teorii formalnej, ale w praktyce (języki programowania) wiele rzeczy przytacza się w zamortyzowanym czasie. Na przykład Quicksort jest często wyświetlany jako ale tak naprawdę jest .

O (\log n)

$O(\log n)$

O (n^{2})

$O(n^2)$

— edA-qa mort-ora-y

4

@ edA-qamort-ora-y: (1) Masz na myśli , a nie . (2) Nie to oznacza „ zamortyzowany czas ”; masz na myśli „ oczekiwany czas ” lub mniej formalnie „typowy czas”.

O (n \log n)

$O(n\log n)$

O (\log n)

$O(\log n)$

— JeffE

1

Nikt nie zajął się (dla mnie) bardziej interesującym pytaniem postawionym powyżej: które algorytmy sortowania (jeśli istnieją) mają tę właściwość, że jeśli komparator jest rzutem monetą, to wynikiem jest jednolita permutacja.

— Joe

13

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:

Porównanie dwóch unikalnych elementów nigdy nie jest wykonywane dwukrotnie w tym samym sortowaniu i / lub
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.

— KeithS
źródło

Czy warunek 2 obejmowałby również szybkie sortowanie? Czy byłby to raczej trzeci warunek, że każda iteracja jest mniejsza niż poprzednia.

— edA-qa mort-ora-y

Moim zdaniem QuickSort byłby objęty obydwoma warunkami. W wydajnych QuickSorts wybierasz oś przestawną, a następnie porównujesz z nią każdy element i zamieniasz elementy znajdujące się po niewłaściwej „stronie” osi przestawnej. Po ułożeniu elementów funkcja zwraca QuickSort (po lewej) + pivot + QuickSort (po prawej), a pivot nie jest przenoszony na niższe poziomy. Tak więc oba warunki są prawdziwe; nigdy nie porównujesz żadnego unikalnego a i b więcej niż jeden raz, i ustaliłeś indeks osi obrotu do czasu, gdy zakończysz układanie pozostałych elementów.

— KeithS

Świetna odpowiedź, ale nie zgadzam się z tobą w sprawie BubbleSort. Korzystając ze spójnego komparatora, na i-tej iteracji BubbleSort wie, że ostatnie elementy i-1 znajdują się na ich ostatecznym miejscu, a każda rozsądna implementacja BubbleSort będzie przechodzić przez mniejszą liczbę elementów przy każdej iteracji, więc powinna również przestać po iteracjach .

— Boris Trayvas

Po chwili namysłu chciałbym się z tobą zgodzić; po przejściu X największe wartości X znajdują się na swoim miejscu, dzięki czemu można zmniejszyć przestrzeń problemową przy każdym przejściu, dzięki czemu wydajny algorytm spełnia warunek 2.

— Wyedytuję

Musisz być ostrożny przy implementacji Quicksort. Można założyć, że poszukiwanie elementu nie mniejszego niż pivot zakończy się, gdy napotkamy pivot lub element większy niż pivot; niekoniecznie tak by było.

— gnasher729,

10

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

\sum_{ja = 1}^{k} ja {2)}^{- ja} \leq \sum_{ja = 1}^{\infty} ja {2)}^{- ja} = 2)

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

$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.

— cody
źródło

Quicksort może powtarzać porównania, jeśli ten sam element zostanie wybrany jako oś obrotu więcej niż jeden raz (może występować wiele razy na liście).

— Raphael

2

@Raphael: Mój wybór słów był słaby: miałem na myśli powtarzanie porównań pomiędzy występującymi elementami, które nie występują więcej niż raz w Quicksort.

— cody

1

@Gilles: Mogę się mylić, ale nie sądzę, aby przechodniość porównywania była kluczowa dla czasu działania większości algorytmów sortujących; z pewnością poprawność , ale to nie było przedmiotem pytania.

— cody

@Gilles: OP nie pyta o algorytmy, które faktycznie sortują. Pyta o to, co dzieje się ze standardowymi algorytmami sortowania, gdy wszystkie porównania są zastępowane rzutami monetą. Powstałe algorytmy nie sortują się (z małym prawdopodobieństwem), ale nadal są dobrze zdefiniowanymi algorytmami.

— JeffE

@JeffE Teraz to rozumiem. Nie tak początkowo czytałem pytanie, ale biorąc pod uwagę komentarze pytającego, właśnie o to chodziło.

— Gilles 'SO - przestań być zły'

2

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

— Thomas Eding
źródło

Czy Haskell czy Caml są teraz modne?

— Yai0Phah

Nie mam pojęcia. Ale Haskell jest moim ulubionym językiem, więc zaprogramowałem to w nim; dopasowanie wzoru ułatwiło to.

— Thomas Eding,

0

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.

— Petr Pudlák
źródło