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

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

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. $O(\log n)$ $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(\log^2 n)$

ds.algorithms sorting sorting-network

— Chao Xu
źródło

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 ?

\log n

$\log n$

— Jeremy

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

(a_{1}, . . ., a_{n})

$(a_1, ..., a_n)$

(b_{1}, . . ., b_{n})

$(b_1, ..., b_n)$

a_{1}

$a_1$

b_{1}, . . ., b_{n}

$b_1, ..., b_n$

Ω (n)

$\Omega(n)$

— Jukka Suomela

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 (\log^{2} n)

$O(\log^2 n)$

— Chao Xu

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.

(a_{1}, \dots, a_{n})

$(a_1,\ldots,a_n)$

(b_{1}, \dots, b_{n})

$(b_1,\ldots,b_n)$

n

$n$

\lg n

$\lg n$

— Jeremy

Teraz pojawia się nowe powiązane (ale miejmy nadzieję o wiele łatwiejsze) pytanie: cstheory.stackexchange.com/questions/8073/...

— Jukka Suomela

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ć

Richard Cole: „ Parallel Merge Sort ”. SIAM J. Comput. 17 (4): 770–785 (1988).

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(\log n)$ $O(1)$

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

MT Goodrich, SR Kosaraju: „ Sortowanie na maszynie ze wskaźnikiem równoległym z aplikacjami do ustawiania oceny ekspresji ”. J. ACM 43 (2): 331-361 (1996).

— 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(\log n)$

O (\log n)

$O(\log n)$

— Vk1