Sortowanie ze średnią porównań

Czy istnieje algorytm sortowania oparty na porównaniu, który wykorzystuje średnie porównania ? $\mathrm{lg}(n!)+o(n)$

Istnienie algorytmu porównania najgorszego przypadku jest otwartym problemem, ale średni przypadek wystarcza dla algorytmu losowego z oczekiwanym porównania dla każdego wkładu. Znaczenie polega na tym, że są to porównania z optymalnych, marnując średnio tylko porównań na element. $\mathrm{lg}(n!)+o(n)$ $\mathrm{lg}(n!)+o(n)$ $\mathrm{lg}(n!)+o(n)$ $o(n)$ $o(1)$

Ponieważ mam już taki algorytm, włączam go jako odpowiedź (używając formatu Q / A ), ale z zadowoleniem przyjmuję dodatkowe odpowiedzi, w tym inne algorytmy, czy taki algorytm był już znany, poprawiając $o(n)$ , a najgorsze- case $\mathrm{lg}(n!)+o(n)$ .

Wcześniejsza praca:
sortowanie według scalania używa $\mathrm{lg}(n!)+ Θ(n)$ porównań (nawet w najgorszym przypadku).
Sortowanie z wstawianiem korespondencji (znane również jako sortowanie Forda i Johnsona) również używa $\mathrm{lg}(n!)+ Θ(n)$ porównań, ale ze znacznie mniejszą stałą w $Θ(n)$ .
Poprawiona średnia złożoność sortowania opartego na porównaniu (autorstwa Kazuo Iwamy i Junichi Teruyama) - ich algorytm wstawiania (1,2) przypomina część mojej odpowiedzi poniżej.

cc.complexity-theory ds.algorithms sorting

— Dmytro Taranovsky
źródło

To pytanie pokrywa się z optymalnym losowym sortowaniem porównawczym , ale biorąc pod uwagę inny nacisk (tutaj specyficzne zachowanie asymptotyczne - w porównaniu z ogólnym stanem wiedzy, wszystkimi wielkościami wejściowymi i różnicą od najgorszego przypadku), zdecydowałem się na nowe pytanie.

— Dmytro Taranovsky,

Aktualizacja: Rozszerzyłem tę odpowiedź na artykuł Sortowanie ze średnią porównań $\mathrm{lg}(n!)+o(n)$ .

Tak, taki algorytm istnieje. Udowodnię tylko, że , ale przy założeniu prawdopodobnej randomizacji otrzymujemy również . Opiszę także próbę dla i . $\mathrm{lg}(n!)+o(n)$ $\mathrm{lg}(n!)+O(n^{1-ε})$ $n^{0.5+o(1)}$ $O(n^{0.5-ε})$

Możemy założyć, że wszystkie elementy są różne, w razie potrzeby dodając do nich adnotacje; przeciętny przypadek wykorzystuje różne elementy w losowej kolejności. Możemy obliczyć średnią liczbę porównań, dodając utratę entropii dla każdego porównania w stosunku do użycia uczciwej monety.

Punktem wyjścia jest wstawianie sortowania z zasadą poszukiwania binarnego zdecydować, gdzie umieścić następny element do posortowanej podzbiór . Gdy , insercja wykorzystuje co najwyżej porównań, które (pod względem entropii) są optymalne do współczynnika addytywnego (a dla złożoności średnich przypadków również działa). Teraz, kiedynie jest bliskie potędze 2, wstawienie elementu jest nieoptymalne (nawet w średnim przypadku i niezależnie od tego, jak równoważymy każde zapytanie), ale jeśli marnujemy porównania , możemy skierować do mniej więcej równomiernego rozkładu w odstępie czasu $S$ $(1-ε)2^m ≤ |S| ≤ 2^m-1$ $m$ $O(ε)$ $2^m ≤ |S| ≤ (1+ε) 2^m$ $|S|$ $A$ $o(1)$ $A$ $S$ o długości zbliżonej do potęgi 2, uzyskujemy pożądaną optymalność.

Osiągamy to poprzez dodawanie elementów w partiach, a czasem efektywne porównywanie ze sobą elementów partii, tak że przedział odpowiadający pierwiastkowi zmniejsza się quasi-losowo (i wraz z rozkładem prawdopodobieństwa wewnątrz przedziału prawie jednolity), a gdy długość odstępu jest wystarczająco blisko do potęgi 2, wykonując przeszukiwanie binarne wstawianie . $S$ $A$ $A$ $A$

Typowe konstrukcje

Będziemy trzymać podzbiór elementów segregowanych i niesegregowanych dla każdego elementu , będziemy śledzić minimalnego odstępu z gdzie jest znany być zlokalizowany. jest długością ; wynika z tożsamości przedziałów. $S$ $A$ $I_A$ $S$ $A$ $|I_A|$ $I_A$ $I_A=I_B$

Niech będzie: Porównaj z , a następnie (w losowej kolejności) porównaj i z odpowiednimi elementami dopóki ich odstępy nie będą rozłączne (lub będą miały długość 1). Element jest wybierany (w spójny sposób), aby prawdopodobieństwo porównania było jak najbliższe 1/2, przy założeniu, że gdy wywoływane jest , rozkłada się równomiernie na . Ze względu na rozłączność na końcu zachowuje założenie jednolitości. $\mathrm{Compare}(A,B)$ $A$ $B$ $A$ $B$ $S$ $S$ $\mathrm{Compare}$ $(A,B)$ $I_A⨯I_B$ $\mathrm{Compare}$

Poniższe sekcje można odczytywać niezależnie od siebie.

algorytm $\mathrm{lg}(n!)+o(n)$

Biorąc pod uwagę: posortowaną listę i partię nieposortowanych elementów; ; nieposortowanej elementy są losowo w stosunku do . $S$ $m$ $m∈ω(1)∩o(|S|)$ $S$

Powtórz (1) - (3), gdy jest to możliwe:
1. Wybierz dwa elementy i z partii z (dowolny wybór będzie działał). 2. Uruchom . 3. Jeżelijest wystarczająco blisko mocy 2 ^{(uwaga 1)} usuń z partii (nie zapominając o ); i zrobić podobnie z . Wreszcie: wstaw wszystkie elementy do i zakończ sortowanie. $A$ $B$ $I_A=I_B$
$\mathrm{Compare}(A,B)$
$|I_A|$ $A$ $I_A$ $B$
$S$

Uwaga 1: W przypadku „wystarczająco blisko” każdy błąd względny (jako funkcja ) działa, dopóki elementy zostaną usunięte w kroku (4) (możliwe dzięki uwadze 2). Zgodnie z domniemanym założeniem randomizacji, użycie błędu względnego przechwytuje elementy , pozwalając na średni algorytm sortowania porównania. $o(1)$ $m$ $m-o(m)$ $c \log \log m / \log m$ $m(1-\log^{-Θ(c)}m)$ $\mathrm{lg}(n!)+O(n \log \log n / \log n)$

Uwaga 2: Ponieważ ta sama sekwencja porównań prowadzi do tego samego interwału granicznego, prawie wszystkie elementy przejdą krok (1) razy (chyba że zostaną usunięte w kroku 4). Na początku, jeśli i wybieramy , porównujemy z elementem , a każde zastosowanie kroku (3) do ma prawdopodobieństwo zmniejszeniarazy . Teraz dla każdego stosunku który nie jest racjonalną potęgą 2, mamy , więc otrzymujemy $Ω(\log m)$ $A < B$ $A$ $A$ $S[≈(1-1/\sqrt{2})|S|]$ $A$ $O(1)$ $|I_A|$ $≈1/(1-1/\sqrt{2})$ $a>1$ $∀ε>0 ∀d>0 ∃m,n∈\mathbb{N} \,\, 1-ε < \frac{a^m}{d2^n} < 1+ε$ $o(n)$ uwiązany.

Prawdopodobny algorytm $\mathrm{lg}(n!)+O(n^{1-ε})$

Modulo założenie randomizacji, możemy osiągnąć średnie porównania w następujący sposób. $\mathrm{lg}(n!)+O(n^{1-ε})$

Losowo potasuj elementy i posortuj pierwszą połowę na listę , zachowując drugą połowę jako nieposortowaną partię. $S$
Powtarzaj, aż partia będzie pusta:
losowo wybierz . Niech . Jeśli jest pusty, usunąć ze wsadu i wkładki do . Inaczej: $A∈\text{batch}$ $G = \{ B∈\text{batch}: |P(A < B) - 0.5| < n^{-0.51ε} \}$ $G$ $A$ $S$
1. Jeśli istnieje taki, że z prawdopodobieństwem (powiedz ≥0,05), powodujew granicach błędu względnego o sile 2, uruchom i jeśli się powiedzie (tj. jest w granicach względnego błędu o sile 2) należy usunąć ze wsadu i wkładki do . $B∈G$ $Θ(1)$ $\mathrm{Compare}(A,B)$ $|I_A|$ $n^{-ε}$ $\mathrm{Compare}(A,B)$ $|I_A|$ $n^{-ε}$ $A$ $S$
2. Jeśli nie ma takiego , uruchom dla losowego . $B∈G$ $\mathrm{Compare}(A,B)$ $B∈G$

Jeśli nasze założenie randomizacji się sprawdzi (tzn. Rozkład długości przedziałów i pozycji jest wystarczająco losowy), to przez większą część procesu typowe można skutecznie porównać z wyborem elementów (z różne długości przedziałów). Dlatego zazwyczaj możemy wybrać porównanie dla (1) powyżej, a jeśli nie będziemy mieli szczęścia z wynikiem porównania, nadal mamy szanse , osiągając (jeśli jest wystarczająco małe, powiedzmy 0,01) a Algorytm porównania . Z pewnymi zmianami i przybliżeniami obliczenie całkowite może być quasilinearne: biorąc pod uwagę element $A$ $n^{Θ(1)}$ $n^{Θ(1)}$ $Θ(\log n)$ $ε$ $\mathrm{lg}(n!)+O(n^{1-ε})$ $A$ , Obliczyć długość interwału obiecujące, a potem patrzeć sz prawej przybliżonej centrum i interwałowych długościach. $B$

Istnieje wiele sposobów na zoptymalizowanie porównań, ale przeszkodą jest to, że każde porównanie może być pechowe i mamy ograniczoną liczbę porównań. Jeśli po optymalizacji wykonuje średnio 4 porównania i „udaje się” z prawdopodobieństwem 1/4, otrzymujemy . $\mathrm{Compare}(A,B)$ $ε≈(1-ε)/4/\log_{4/3} 2 ≈ 0.09$

Być może znacznie lepszym podejściem jest czekanie, aż przedział zbliża się do potęgi 2, kontrolując nie poszczególne długości przedziałów, ale rozkłady długości.

Próba algorytmu $\mathrm{lg}(n!)+n^{0.5+o(1)}$

Załóżmy, że i otrzymujemy nieposortowaną partię elementów z przedziałami , zzwykle i rozmieszczone równomiernie (do błędu losowego i utrzymujące z wystarczającą precyzją, nawet jeśli uwarunkowane ). Następnie możemy posortować elementy marnujące średnio porównania w następujący sposób: (*) Wstaw wszystkie elementy w kolejności ich początkowego . W ten sposób wszystkie elementy są wstawiane, gdy ich długość przedziału jest zbliżona do potęgi 2. $|S|=n$ $n$ $I_A$ $|I_A|$ $n^{1-o(1)}$ $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ $A < S[i]$ $n^{0.5+o(1)}$
$\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

Algorytm sortowania będą: Losowo przetasować listę i sortować pierwszej połowie . Aby wstawić drugą połowę, ustaw właściwy rozkład i wykonaj powyższe (*). $S$

Aby zrobić prawidłowa dystrybucja, możemy zrobić rozkład „losowy”, a następnie wstrzymać właściwą część elementów dla każdego podczas losowania reszty (w razie potrzeby powtarzanie). Jednak chociaż powinno to poprawić globalnie, nie wiemy, czy można nim sterować lokalnie z wymaganą precyzją (stąd słowo „próba” powyżej). $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$ $|I_A|/2^{\lfloor \mathrm{lg} |I_A| \rfloor}$ $\frac{|I_A|}{2^{\lfloor \mathrm{lg} |I_A| \rfloor}}$

Aby utworzyć rozkład „losowy”, możemy losowo użyć z , z tym wyjątkiem, że przy początkowym wszystkie identyczne, nie oczekujemy randomizacji na sublogarytmicznej głębokości (tzn. z wystarczająco długo). Przypuszczam jednak, że otrzymujemy randomizację na głębokości sublogarytmicznej przy użyciu uogólnień (prawdopodobnie każdy rozsądny wybór zadziała) elementów do elementów : Jeśli utrzymamy splątane elementy (tj. połączone za pomocą wyników porównania), powinniśmy mieć o noncommuting wyborów dla każdego porównania z . To powinno pozwolić $\mathrm{Compare}(A,B)$ $P(A < B)≈0.5$ $I_A$ $I_A$ $\mathrm{Compare}$ $k=ω(1)$ $k=ω(1)$ $k$ $S$ $O(\log_k n + \log k)$ głębokość randomizacji, zgodnie z potrzebami (przy założeniu, że nie jest zbyt duża, ponieważ potrzebujemy głębokości aby rozdzielić elementy). Oczekuję, że obliczenie może być quasilinear, jeśli używa się wystarczająco małego . $k$ $Θ(\log k)$ $k$

Ponieważ porównanie z prawdopodobieństwem tak tylko marnuje entropię , początkowa randomizacja i niewielka niejednorodność elementów w ich przedziałach granicznych powinna wymagać tylko odpady entropijne. Jeśli kształtowanie rozkładu powiedzie się wystarczająco dobrze, odpady entropijne wynikają przede wszystkim z niedopasowania długości przedziałów podczas (*) (stąd ). $1/2+n^{-0.5}$ $O(1/n)$ $n^{o(1)}$ $n^{0.5+o(1)}$

Możliwa kombinacja : $\mathrm{lg}(n!)+O(n^{0.5-ε})$ Jeśli kształtowanie rozkładu działa wystarczająco dobrze, a wielkość partii jest równa i selektywnie odrzucaj w (*) (powyżej), możemy wstawić wszystkie elementy oprócz tych z odpadami entropii w następujący sposób. Podziel na prawie równych przedziałach, a gdy podczas wstawiania osiądzie na przedziale, odrzuć (tj. Anuluj wstawienie), jeśli przedział jest zbyt długi, zmniejszając w ten sposób zmienność długości tych przedziałów $|S|+n^{0.5+ε}$ $≈n^{0.5+ε}$ $≈n^{0.5+ε}$ $n^{0.5-ε/2+o(1)}$ $S$ $n^ε$ $I_A$ $Θ(n^{ε/2})$ razy, co z kolei zmniejsza w zależności od potrzeb zmiany długości przedziałów losowych razy . Teraz możemy użyć powyższego algorytmu , aby wstawić pozostałe elementy marnotrawstwem jeśli jest małe wystarczająco. $n^{1-o(1)}$ $n^{ε/2-o(1)}$ $\mathrm{lg}(n!)+O(n^{1-ε})$ $O(n^{0.5-ε'})$ $ε$

Złożoność sortowania w najgorszym przypadku: Najprawdopodobniej istnieje algorytm sortowania z porównaniami najgorszych przypadków. Aby znaleźć medianę, istnieje liniowa przerwa między średnim przypadkiem (porównania ) a najgorszym przypadkiem (porównania co najmniej ). Jednak w przypadku sortowania istnieje duża swoboda w organizowaniu porównań i znajdowaniu nowych algorytmów sortowania. $\mathrm{lg}(n!)+o(n)$ $1.5n+o(n)$ $(2+ε)n-O(1)$

— Dmytro Taranovsky
źródło

Myślę, że powinieneś napisać to jako artykuł.

— Emil Jeřábek

@ EmilJeřábek Zgoda. Jako witryna na poziomie badawczym wiele pytań i odpowiedzi tutaj jest mini-papierami, ale biorąc pod uwagę ich długość i znaczenie, pożądana jest formalna praca. Daj mi znać (na dmytro@mit.edu) o tym, które części należy rozwinąć w artykule (z tą odpowiedzią pozostającą w zwięzłej wersji).

— Dmytro Taranovsky