Algorytm sortowania, dzięki któremu każdy element jest porównywany razy i nie zależy od sieci sortującej

39

Czy istnieją znane algorytmy porównywania, które nie ograniczają się do sortowania sieci, tak że każdy element jest porównywany razy?O(logn)

O ile mi wiadomo, jedynym sposobem sortowania za pomocą porównania na każdym elemencie jest zbudowanie sieci sortującej AKS dla danych wejściowych i uruchomienie danych wejściowych w sieci sortującej.nO(logn)n

AKS nie jest łatwy do wdrożenia i ma niepraktyczny stały współczynnik, dlatego istnieją motywacje do poszukiwania innych algorytmów.

Algorytm z porównań na pozycji, która nie wydaje się sugerować, sortowania sieci jest prezentowany tutaj . (iirc, zostało to po raz pierwszy zaprezentowane przez Roba Johnsona na seminarium algorytmicznym Stony Brook).O(log2n)

Chao Xu
źródło
2
Nie rozumiem pytania: wiele sekwencyjnych algorytmów wydaje się odpowiadać twojej prośbie. np. Sortuj scalenie jest klasycznym algorytmem sortowania i nie dokonuje więcej niż porównania na element. Może pytasz o algorytmy sortowania równoległego ? logn
Jeremy
4
@Jeremy: Jeśli scalisz dwie listy i , możesz skończyć na porównywaniu z każdą z , to znaczy Porównania na jeden element. I to był tylko jeden krok „scalenia”. Oczywiście średnia liczba porównań jest z konieczności niewielka, ale pytanie dotyczy złożoności najgorszego przypadku . ( b 1 , . . . , B n ) 1 b 1 , . . . , b n Ω ( n )(a1,...,an)(b1,...,bn)a1b1,...,bnΩ(n)
Jukka Suomela
6
Wierzę, że to możliwe. Sieci sortujące są nieświadome danych i mają z góry określony sposób porównań, ale algorytm sortujący może być w stanie wybierać między różnymi zestawami operacji zależnymi od danych. Można zmodyfikować sortowanie korespondencji seryjnej w algorytmie z porównaniem dla każdego elementu i nie wydaje się sugerować sieci sortującej reddit.com/comments/9jqsi/…O(log2n)
Chao Xu
1
Jukka: Dzięki, rozumiem o co ci chodzi. Ale to tylko przy użyciu naiwnego scalania: można połączyć z za pomocą podwójnego wyszukiwania, aby umieścić każdy element, co w dalszym ciągu jest porównaniami w najgorszym przypadku, ale porównań na element maksymalnie, co daje wersję sortowania scalania, o której wspomina Chao. ( b 1 , , b n ) n lg n(a1,,an)(b1,,bn)nlgn
Jeremy
2
Teraz pojawia się nowe powiązane (ale miejmy nadzieję o wiele łatwiejsze) pytanie: cstheory.stackexchange.com/questions/8073/...
Jukka Suomela

Odpowiedzi:

17

Po omówieniu tego z Michaelem T. Goodrichem wydaje się, że algorytm sortowania równoległego Cole'a dla EREW PRAM spełnia swoje zadanie. Widzieć

W tym algorytmie są rundy i w każdej rundzie każdy element bierze udział w porównaniach . (Trzeba zrozumieć algorytm, aby zobaczyć, że nie nadużywamy robienia kopii każdego elementu.)O ( 1 )O(logn)O(1)

Rozszerzenie tego algorytmu dla maszyny wskaźnika równoległego podano w

ktoś
źródło
Chcielibyśmy wiedzieć, kim jesteś! : D
Tayfun Zapłać
@someone to Sergio Cabello
ktoś
@ktoś. Ty za tę odpowiedź. Wymienia wyniki w modelu EREW. Ponieważ jego wyłączny model odczytu i wyłączny model zapisu oznacza, że ​​wszystkie lokalizacje są dotykane co najwyżej O (1) w każdej rundzie, a tym samym razem. Czy oznacza to prosty algorytm znajdowania mediany w pamięci RAM (lub nawet modelu EREW) przy użyciu porównań na element? O ( log n )O(logn)O(logn)
Vk1