Czy istnieją znane algorytmy porównywania, które nie ograniczają się do sortowania sieci, tak że każdy element jest porównywany razy?
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.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).
ds.algorithms
sorting
sorting-network
Chao Xu
źródło
źródło
Odpowiedzi:
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
źródło