Sieć sortująca

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

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.

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.

SimpleSortingNetworkFullOperation.svg
(c) Oskar Sigvardsson, CC BY 3.0

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)2) (a więc wielkość O(n (log n)2)). 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 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 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

Linki zewnętrzne

Media użyte na tej stronie

Six-wire-pyramid-sorting-network.svg
(c) Oskar Sigvardsson z angielskiej Wikipedii, CC BY 3.0
Six wire sorting network based on insertion sort and bubble sort
Recursive-bubble-sorting-network.svg
(c) Oskar Sigvardsson z angielskiej Wikipedii, CC BY 3.0
A sorting network recursively constructed by selecting the largest element and sorting the smaller sublist
Sorting-network-comparator-demonstration.svg
(c) --Oskar, CC BY 3.0
A simple demonstration of a the function of a comparator in a Sorting network
SimpleSortingNetworkFullOperation.svg
(c) Oskar Sigvardsson, CC BY 3.0
The entire operation of a simple sorting network
Six-wire-bubble-sorting-network.svg
(c) Oskar Sigvardsson z angielskiej Wikipedii, CC BY 3.0
Six wire sorting network based on bubble sort
Recursive-insertion-sorting-network.svg
(c) Oskar Sigvardsson z angielskiej Wikipedii, CC BY 3.0
A sorting network recursively constructed by inserting an element in a sorted array
Six-wire-insertion-sorting-network.svg
(c) Oskar Sigvardsson z angielskiej Wikipedii, CC BY 3.0
Six wire sorting network based on insertion sort