Sieć sortująca

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.

Prosta sieć sortująca składająca się z czterech przewodów i pięciu łączników

Wprowadzenie

Demonstracja działania komparatora w sieci sortującej

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.

Sieci sortujące przez wstawianie i wybieranie

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

Sieć sortująca skonstruowana rekurencyjnie. Najpierw największa wartość przenoszona jest na dół, a następnie sortowana jest reszta wartości. Całość oparta na sortowaniu bąbelkowym

Sieć sortująca skonstruowana rekurencyjnie. Najpierw sortowane jest pierwsze n przewodów, a następnie dokładana jest pozostająca wartość. Całość oparta na sortowaniu przez wstawianie

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 bąbelkowo

Sieć sortująca przez wstawianie

Kiedy zezwalamy na równoczesne działanie komparatorów, obie sieci są identyczne

Wydajne sieci

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.

Zasada zero-jeden

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

Optymalne sortowanie

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.

Bibliografia

• 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.).

Linki zewnętrzne

• 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.)