Sieć sortująca – Wikipedia, wolna encyklopedia

Sieć sortująca to abstrakcyjny, matematyczny model sieci, składającej się z przewodów i modułów porównujących (komparatorów), używanej do sortowania sekwencji liczb. Każdy moduł porównujący łączy dwa przewody i sortuje dwie wartości, wyprowadzając mniejszą na jeden przewód i większą na drugi. Pomimo prostoty modelu, teoria sieci sortujących jest zaskakująco głęboka i złożona.

Sieć sortująca składa się z dwóch rodzajów elementów: komparatorów i przewodów. Każdy przewód przenosi wartość, zaś każdy komparator podłączony jest do dwóch przewodów, które stanowią zarazem jego wejścia i wyjścia. Kiedy wartości docierają do komparatora, moduł wysyła mniejszą wartość na górny przewód, a większą na dolny. Sieć przewodów i komparatorów, które poprawnie sortują wszystkie możliwe wartości wejściowe w porządku rosnącym nazywamy siecią sortującą.

Działanie prostej sieci sortującej przedstawione jest poniżej. Łatwo zobaczyć dlaczego ta sieć poprawnie posortuje wartości wejściowe; pierwsze cztery komparatory prześlą największą wartość na dół i „wyniosą” najmniejszą do góry. Ostatni komparator posortuje wartości z dwóch środkowych przewodów.

Możemy łatwo stworzyć sieć dowolnej wielkości rekurencyjnie stosując zasady wstawiania i wybierania. Zakładając, że mamy sieć sortującą wielkości n, możemy stworzyć sieć wielkości n+1 wstawiając dodatkową liczbę do już posortowanej podsieci (stosując metodę sortowania przez wstawianie). Możemy także zrobić to samo „wybierając” najmniejszą wartość z danych wejściowych i sortując rekurencyjnie pozostałe wartość (stosując metodę sortowania bąbelkowego).

Struktura tych dwóch sieci jest bardzo podobna. Jeśli założymy, że komparatory mogą działać równocześnie, to sieci te są w praktyce identyczne.

Sieć sortująca przez wstawianie ma głębokość O(n), co czynią ją niepraktyczną. Istnieją podobne sieci, które osiągają głębokość O((log n)²) (a więc wielkość O(n (log n)²)). Przykłady takich sieci to Batcher odd-even mergesort, a także sieci oparte na sortowaniu bitonicznym i sortowanie Shella. Te sieci są często używane w praktyce.

O ile łatwo jest udowodnić poprawność niektórych sieci sortujących (jak powyższe przykłady używające sortowania przez wstawianie/sortowania bąbelkowego), o tyle przy innych jest to dużo trudniejsze. Istnieje ${\displaystyle n!}$ permutacji liczb w n-przewodowej sieci i przetestowanie ich wszystkich może pochłonąć znaczną ilość czasu, zwłaszcza przy dużych sieciach. Jednak, dzięki tak zwanej zasadzie zero-jeden, wystarcza o wiele mniej prób aby przetestować poprawność sieci sortującej.

Zasada zero-jeden mówi, że sieć sortująca jest poprawna, jeśli może posortować wszystkie ${\displaystyle 2^{n}}$ sekwencji zer i jedynek. Zasada drastycznie obcina liczbę niezbędnych testów, przez co jest powszechnie używana przy konstrukcji sieci sortujących.

Dowód jest szczególnym przypadkiem twierdzenia Bouriciusa, udowodnionego przez W. G. Bouriciusa w 1954 roku.

Efektywność sieci sortującej może być zmierzone jej całkowitą wielkością (ilością użytych komparatorów) lub głębokością (maksymalną ilością komparatorów prowadzących od jednego z wejść do jednego z wyjść). Najlepszą sieć sortującą odkryli Ajtai, Komlós i Szemerédi. Osiąga ona głębokość O(log n), wielkość O(n log n) dla n wejść, i jest asymptotycznie optymalna. Uproszczona wersja sieci AKS została opisana przez Patersona. Mimo że jest to ważne odkrycie teoretyczne, sieć AKS ma niewielkie zastosowanie praktyczne z powodu ogromnych stałych liniowych ukrywających się w notacji dużego O. Poszukiwanie sieci sortujących wielkości cn log n dla małego c pozostaje ważnym, otwartym problemem.

Dla zakresu od 1 do 8 wejść optymalne sieci sortujące są znane. Mają one odpowiednio 0, 1, 3, 5, 9, 12, 16 i 19 komparatorów (Knuth, 1997 r.). Optymalne głębokości są natomiast znane aż do 10 wejść i wynoszą odpowiednio 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.

• O. Angel, A.E. Holroyd, D. Romik, B. Virag, Random Sorting Networks, Adv. in Math., 215(2):839–868, 2007.
• K.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307–314 (1968).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 27: Sorting Networks, s. 704–724.
• D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, s. 219–247.
• M.S.M.S. Paterson M.S.M.S., Improved sorting networks with O(logN) depth, „Algorithmica”, 5 (1-4), 1990, s. 75–92, DOI: 10.1007/BF01840378, ISSN 0178-4617  (ang.).

• Sieci sortujące (ang.)
• Sieci sortujące. cs.uky.edu. [zarchiwizowane z tego adresu (2008-01-16)]. (ang.)
• Lista sieci sortujących (ang.)
• Sieci sortujące i algorytm END (ang.)