Strona główna » Algorytmy » Sortowanie » Bardzo Wolne Sortowanie
 

Bardzo Wolne Sortowanie

Wstęp

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.

Algorytm

Opis

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.

Przykład

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łanieTablicaKomentarzWynik
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ść

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
n2n·log(n)
105910024
2038940060
301459900103
4041231600148
5098272500196
60207973600246
70402674900298
80729016400351
901251478100405
10020565710000461

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.

Implementacja

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.

C++
C#
  1. static void sortuj(int[] tab, int L, int P) {
  2.   if (L >= P) return;
  3.   int m = (P + L) / 2;
  4.   sortuj(tab, L, m);
  5.   sortuj(tab, m + 1, P);
  6.   if (tab[P] < tab[m]) {
  7.     int t = tab[P];
  8.     tab[P] = tab[m];
  9.     tab[m] = t;
  10.   }
  11.   sortuj(tab, L, P - 1);
  12. }

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

Testowanie funkcji

W celu przetestowania napisanej funkcji sortuj() można skorzystać z poniższego fragmentu kodu.

C++
C#
  1. static void Main(string[] args) {
  2.   Console.Write("Podaj ile jest elementow\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   int[] tab = new int[n];
  5.   Console.WriteLine("Podaj elementy:");
  6.   for (int i = 0; i < n; i++)
  7.     tab[i] = Convert.ToInt32(Console.ReadLine());
  8.   sortuj(tab);
  9.   Console.WriteLine("Po posortowaniu:");
  10.   for (int i = 0; i < n; i++)
  11.     Console.Write("{0} ", tab[i]);
  12.   Console.ReadKey();
  13. }

Zadania

Zadanie 1

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.