Bardzo Wolne Sortowanie to najgorszy możliwy algorytm do sortowania danych. Nie znajduje on praktycznego zastosowania. Został on opracowany przez A. Broder and J. Stolfi tak, aby wykorzystywał metodę "Dziel i poddawaj się". Algorytm posiada złożoność obliczeniową gorszą od sortowania bąbelkowego i jego złożoność nie zależy od danych wejściowych.
Twórcy algorytmu początkowo opracowali całkiem prosty algorytm sortowania. Polegał on na tym, że sortując dane rosnąco wybieramy z nieposortowanej części maksymalny element, a następnie przesuwamy go na koniec. Proces ten powtarzamy tak długo, aż wszystkie elementy zostaną posortowane. Jak można zauważyć oznaczałoby to do wykonania dla n elementów w tablicy T(n) = n + n - 1 + n - 2 + .. + 1 = n(n + 1)/2 co daje złożoność O(n) = n2. Wtedy złożoność wychodziłaby podobna do tej znanej z najmniej optymalnych sortowań. Jednak autorzy zastosowali dodatkowo metodą "Dziel i poddawaj się".
Podczas sortowania danych są one podzielone początkowo na dwie części, które są sortowane oddzielne. Potem rekurecyjnie każda z części jest sortowana poprzez ponowne podzielenie na dwie części. Oczywiście po posortowaniu obu połówek cały ciąg zostaje posortowany jeszcze raz przedstawionym wcześniej algorytmem. W ten sposób otrzymano wysoce nieoptymalny algorytm, który ma za zadanie pokazać, że dzielenie problemu na podproblemy nie zawsze jest optymalne.
Weźmy tablicę 4 elementów L := {8, 7, 2, 6}. Pierwsze co należy zrobić to podzielić na mniejsze podproblemy, posortować je, a potem złączyć ponownie. Oczywiście dane są dzielone, aż do uzyskania podtablicy wielkości jeden, która jest z racji rozmiaru - posortowana.
| Wywołanie | Tablica | Komentarz | Wynik |
|---|---|---|---|
| 1a | {8, 7, 2, 6} | podział | {8, 7}, {2, 6} |
| 1.1a | {8, 7} | podział | {8}, {7} |
| 1.1.1 | {8} | posortowane | {8} |
| 1.1.2 | {7} | posortowane | {7} |
| 1.1b | {8}, {7} | łączenie i sortowanie | {7, 8} |
| 1.2a | {2, 6} | podział | {2}, {6} |
| 1.2.1 | {2} | posortowane | {2} |
| 1.2.2 | {6} | posortowane | {6} |
| 1.2b | {2}, {6} | łącznie i sortowanie | {2, 6} |
| 1b | {7, 8}, {2, 6} | łącznie i sortowanie | {2, 6, 7, 8} |
Ostatecznie posortowana tablica ma postać P := {2, 6, 7, 8}.
Złożoność tego algorytmu jest bardzo trudno wyznaczyć ze względu na jego bardzo skomplikowaną strukturę. Operacją dominującą jest tutaj niewątpliwie porównanie. W każdym wywołaniu wywołujemy dwa podproblemy oraz problem główny, a potem wykonujemy jedną zamiane. Innymi słowy T(n) = 2T(n/2) + T(n - 1) + 1. Wiadomo, że dla T(0) = 0, T(1) = 1, ponieważ jest to moment w którym "poddajemy" dalsze dzielenie problemu na prostsze podproblemy.
Korzystając ze wzoru można wyprowadzić, że T(2) = 2T(1) + T(1) + 1 = 4. Z kolei T(3) = 2T(1) + T(2) + 1 = 2T(1) + (2T(1) + T(1) + 1) + 1 = 6. Jak można zauważyć początkowo te liczby nie odbiegają znacząco od pozostałych algorytmów. Jednak poniższa tabelka powinna rozwiać wątpliwości, dlaczego jest to Bardzo Wolne Sortowanie:
| Rozmiar tablicy n | Wolne Sortowanie | n2 | n·log(n) |
|---|---|---|---|
| 10 | 59 | 100 | 24 |
| 20 | 389 | 400 | 60 |
| 30 | 1459 | 900 | 103 |
| 40 | 4123 | 1600 | 148 |
| 50 | 9827 | 2500 | 196 |
| 60 | 20797 | 3600 | 246 |
| 70 | 40267 | 4900 | 298 |
| 80 | 72901 | 6400 | 351 |
| 90 | 125147 | 8100 | 405 |
| 100 | 205657 | 10000 | 461 |
Jak można zauważyć algorytm dla zaledwie 100 danych wykonuje aż 446 razy więcej operacji! Co więcej wykazuje się, że nie da rady przybliżyć złożoności przy pomocy wielomianu.
Algorytm sortowania będzie działał rekurencyjnie. Na początku należy sprawdzić czy wybrany obszar podtablicy ma jakikolwiek sens. Potem należy wyznaczyć środkowy element i posortować lewą i prawą część. Potem, aby znaleźć element maksymalny wystarczy porównać ostatnie elementy z każdej części i jeśli zajdzie taka potrzeba to należy je zamienić miejscami. Na koniec należy ponownie wywołać sortowania tablicy, ale bez ostatniego elementu.
(1.) W przedstawionym kodzie zakres to [L, P]. (2.) Sortowanie nie ma sensu jeśli wybrana podtablica ma rozmiar 1 czyli L = P, albo jest niemożliwa do wybrania dla L > P. Potem należy (3.) wyznaczyć środkowy element m i posortować (4.) lewą i (5.) prawą część. Potem (6. - 10.) należy porównać maksymalne elementy z dwóch części i jeśli nie spełniają warunku to zamienić. W ten sposób największy element trafi na koniec nieposortowanej części tablicy. Potem pozostaje (11.) uruchomić sortowanie dla nieposortowanej części tablicy.
W celu przetestowania napisanej funkcji sortuj() można skorzystać z poniższego fragmentu kodu.
Napisz algorytm Wolnego Sortowania według jego pierwotnej wersji. W tablicy o rozmiarze n znajdź element maksymalny i zamień go z ostatnim elementem w tablicy. Dla nieposortowanej części tablicy powtórz wyszukiwanie i zamiane, aż nieposortowana część będzie miała długość 1. Nie używaj do tego celu rekurencji.