Sortowanie wielofazowe

Sortowanie wielofazowe (czasami „polifazowe”, pod wpływem ang. polyphase sort) – algorytm sortowania zewnętrznego wynaleziony przez R. L. Gilstada. Algorytmy sortowania zewnętrznego operują na taśmach lub innych pamięciach o dostępie sekwencyjnym, a ich podstawowym zastosowaniem jest sortowanie danych, których objętość przewyższa wielkość dostępnej pamięci głównej. W takim wypadku tradycyjne algorytmy sortowania są nieprzydatne, gdyż są przystosowane do dostępu swobodnego i znacznie niższych czasów dostępu.

Efektywność

Algorytm sortowania wielofazowego jest algorytmem umożliwiającym pełniejsze wykorzystanie dostępnych taśm niż algorytmy sortowania przez scalanie, łączenie proste oraz łączenie naturalne. Przy użyciu N taśm sortowanie wielofazowe działa zawsze jako łączenie (N-1)-kierunkowe, natomiast liczba potrzebnych przebiegów wynosi w przybliżeniu $\log _{N}n,$ gdzie n jest liczbą elementów do posortowania, a N stopniem operacji łączenia. Jest to znaczna poprawa w stosunku do metod wcześniej wymienionych.

Algorytm

Sortowanie wielofazowe przebiega dwuetapowo:

Pierwszym etapem jest dystrybucja serii z wejścia na pozostałe dostępne taśmy. W przeciwieństwie do wcześniejszych metod sortowania, sortowanie wielofazowe nie wykorzystuje równomiernej dystrybucji serii. Początkowe rozłożenie jest uprzednio obliczane z wykorzystaniem liczb Fibonacciego. Należy zwrócić uwagę, że odpowiednia dystrybucja jest warunkiem koniecznym efektywnego działania algorytmu.

Drugim etapem jest właściwe sortowanie odbywające się z użyciem T-1 taśm w trybie odczytu oraz pojedynczej taśmy w trybie zapisu. Taśma zapisywana nie jest wybierana na stałe, lecz wybierana po każdej iteracji algorytmu.

Algorytm dystrybucji

Dystrybucja dla sortowania wielofazowego jest oparta na Liczbach Fibonacciego rzędu T-1 o poziomie dobranym do liczby serii na wejściu. Ogólny algorytm wygląda następująco:

„Celem” niech będą liczby Fibonacciego T-1 rzędu, poziomu 1
Dokonaj rozdzielenia według nich.
Jeśli cel został osiągnięty, czyli zostało rozdzielonych tyle liczb, ile zakładał cel, oblicz kolejny poziom liczb Fibonacciego. Niech różnica pomiędzy nim a liczbami poprzedniego poziomu tworzy nowy cel. Idź do kroku 2. Jeśli skończyły się serie na wejściu, zakończ działanie.

Algorytm ten działa bardzo dobrze w przypadku, gdy wejściowa liczba serii jest liczbą Fibonacciego. W przeciwnym razie konieczne są jednak pewne modyfikacje.

Analiza przypadków:

Liczba serii będąca liczbą Fibonacciego

Przypadek ten jest niezmiernie rzadki, lecz stosunkowo prosty.

Tabela optymalnych rozkładów serii dla T = 3:

poziom	Taśma 1	Taśma 2	Liczba serii
1	1	1	2
2	2	1	3
3	3	2	5
4	5	3	8
5	8	5	13
6	13	8	21
7	21	13	34
8	34	21	55
9	55	34	89

Warto tu zauważyć, że poziom liczb Fibonacciego zastosowany w procesie dystrybucji rekordów jest jednocześnie liczbą faz, jakiej potrzebuje algorytm do posortowania ciągu (nie licząc fazy dystrybucji).

Przykładowo, sortując 89 serii, algorytm będzie potrzebował 9 przebiegów (faz). Podobnie dla 88 czy 56 rekordów.

Liczba serii niebędąca liczbą Fibonacciego

W tym przypadku należy dodać do ciągu wejściowego tyle serii pustych (ang. dummies), aby wyrównać do najbliższej większej liczby Fibonacciego. Najprostszym skutecznym sposobem rozdysponowania serii pustych jest ich rozłożenie równomierne na wszystkich taśmach. Istnieje wiele rozwiązań tego problemu.

Przykładowe rozdysponowanie 10 serii:

Liczba serii:	rzeczywistych	pustych	łączna
Taśma 1	6	2	8
Taśma 2	4	1	5
Taśma 3	0	0	0

Uwaga! Jest wiele algorytmów umożliwiających dobre rozdysponowanie serii pustych. Ten rozkład nie jest jedynym dobrym, a tylko jedną z wielu możliwości.

Algorytm sortowania

Jako taśmę wejściową, na której znajdują się dane do posortowania obieramy taśmę T (ostatnią).

Przeprowadź dystrybucję z taśmy źródłowej na pozostałe. Taśma źródłowa jest po tej operacji pusta.
Oznacz taśmę ostatnią jako taśmę do zapisu.
Z pozostałych taśm pobierz po jednej serii. Pobrane serie połącz i zapisz na pustej taśmie.
Jeżeli są dostępne serie danych na wszystkich pozostałych taśmach, idź do 2. Jeżeli na taśmie poprzedzającej skończyły się serie, oznacz ją jako taśmę do zapisu.
Jeżeli jest to ostatni etap, zakończ sortowanie (liczba etapów jest z góry znana). W przeciwnym razie idź do 2.

Przykłady

Sortowanie wielofazowe dla liczby taśm T = 4, liczby serii r = 9, długości serii l = 1 bez wstępnego scalania serii przebiega następująco:

wczytanie danych wejściowych

Poszczególne serie rozdzielone są znakiem |

Taśma 1
Taśma 2
Taśma 3
Taśma 4	6 \| 3 \| 20 \| 15 \| 13 \| 8 \| 10 \| 17 \| 1

Dystrybucja (4,3,2)

Dystrybucję przeprowadzamy zgodnie z odpowiednim dla tej liczby serii rozkładem, w tym wypadku 4,3,2 – są to liczby Fibonacciego rzędu 3, poziomu 3. Serie pobieramy z taśmy źródłowej kolejno, bez dodatkowych operacji.

Taśma 1	6 \| 3 \| 20 \| 15
Taśma 2	13 \| 8 \| 10
Taśma 3	17 \| 1
Taśma 4

I Faza

Z każdej zawierającej serie taśmy pobieramy po jednej serii, scalamy sortując i zapisujemy na pustą taśmę. Jeśli na którejś z taśm serie się skończą, przerywamy. Serie na taśmie 4 są, po wykonaniu procedury, posortowanymi trójkami.

Taśma 1	20 \| 15
Taśma 2	10
Taśma 3
Taśma 4	6 13 17 \| 1 3 8

II Faza

Powtarzamy procedurę z poprzedniego kroku pobierając serię z taśmy 1 (20), serię z taśmy 2 (10) oraz serię z taśmy 4 (6, 13, 17), sortujemy i scalamy. Zapisujemy tym razem na taśmę 3 (która, jak łatwo zauważyć, została pusta po poprzednim etapie). Uzyskujemy posortowane serie długości 5 na taśmie 3.

Taśma 1	15
Taśma 2
Taśma 3	6 10 13 17 20
Taśma 4	1 3 8

III Faza

Jako że na każdej taśmie pozostało po jednej serii, scalamy wszystkie na taśmę 2 otrzymując posortowany ciąg 9 liczb (serii).

Taśma 1
Taśma 2	1 3 6 8 10 13 15 17 20
Taśma 3
Taśma 4

Optymalizacja

Sortowanie wielofazowe jest samo w sobie efektywnym algorytmem, jednak w kilku miejscach można, a nawet wskazane jest zastosowanie ulepszeń. Istnieje kilka sposobów ulepszenia procesu sortowania, trzy najbardziej popularne to:

Łączenie serii

W czasie dystrybucji, zamiast rozdzielania kolejnych wyrazów na taśmy stosujemy algorytm podobny jak w sortowaniu naturalnym, tzn. jeśli dwie lub więcej serii na wejściu są już uporządkowane, scalamy je i zapisujemy na taśmę docelową jako jedną serię. Następnie pobieramy kolejny ciąg serii z wejścia i zapisujemy na następną w kolejności taśmę itd. W pesymistycznym przypadku (serie ułożone od największej do najmniejszej) efekt będzie niewidoczny. Istotny jest jednak przypadek średni, gdy na wejściu występuje częściowe uporządkowanie serii – wtedy optymalizacja ta znacznie przyspiesza proces sortowania.

Sortowanie wstępne

Sortowanie wielofazowe nie wymaga użycia dużej ilości pamięci głównej, jeśli jednak jest ona dostępna, można to wykorzystać do zwiększenia wydajności algorytmu. Przed przystąpieniem do dystrybucji należy przeprowadzić sortowanie wstępne w następujący sposób:

pobieramy do pamięci operacyjnej n serii (n musimy dobrać tak, aby n serii mieściło się w pamięci. Ze względu na zmienną długość serii na wejściu, powinno być obliczane dynamicznie.)
sortujemy wczytane n serii wybranym algorytmem (kopiec, qsort, bubblesort itp.)
zapisujemy z powrotem do pamięci zewnętrznej lub od razu zapisujemy nową serię zgodnie z dystrybucją.

W ten sposób uzyskujemy na wejściu dokładnie n razy mniej serii, a każda seria ma długość n. Co za tym idzie – znacząco zmniejszamy liczbę etapów potrzebnych do posortowania danych. Przy dużym n metoda ta daje szczególnie dobre rezultaty.

Zapis i odczyt blokowy

Operacje odczytu z pamięci zewnętrznej są wolne, zatem należy rozważyć wprowadzenie odczytu z dysku całymi blokami do bufora. Każde zmniejszenie liczby operacji odczytu i zapisu na dysk przyspiesza proces sortowania.

Zobacz też

Bibliografia

Niklaus Wirth, Algorytmy + Struktury Danych = Programy, Warszawa, Wyd. Wydawnictwa Naukowo-Techniczne s. 125–135, 1980, ISBN 83-204-2740-1.