Strona główna » Algorytmy » Sortowanie » Komiczne Sortowanie
 

Komiczne Sortowanie

Opis sortowania

Sortowanie Komiczne jest przykładem prostego algorytmu sortowania dowolnych elementów, ale o bardzo wysokiej złożoności obliczeniowej. Z tego powodu należy ten algorytm brać bardziej jako ciekawostkę niż jako faktyczny algorytm do zaimplementowania.

Algorytm

Sortowanie odbywa się w sposób rekurenycjny. Początkowo zakres sortowania jest od pierwszego elementu do ostatniego. Podczas sortowania dla wybranego zakresu porównywane są skrajne elementy zakresu i jeśli potrzebują zamiany to są zamieniane. Następnie sortowana jest pierwsze 2/3 zakresu, następnie ostatnie 2/3 zakresu i na koniec pierwsze 2/3 zakresu. Oczywiście sortowanie jest zaniedbywane, gdy już nie jest możliwy podział zakresy na kolejne podzakresy.

Przykład

Załóżmy, że do posortowania jest tablica L:={6, 1, 7, 5}. Nawiasami kwadratowymi [] został zaznaczony aktualnie przeglądany zakres. Wykonane zostaną następne operacje:

TablicaLewyPrawyKomentarz
{[6,1,7,5]}65Zamiana
{[5,1,7],6}57
{[5,1],7,6}51Zamiana
{1,[5,7],6}57
{[1,5],7,6}15
{1,[5,7,6]}56
{1,[5,7],6}57
{1,5,[7,6]}76Zamiana
{1,[5,6],7}56
{[1,5,6],7}16
{[1,5],6,7}15
{1,[5,6],7}56
{[1,5],6,7}15

Jak można zauważyć już dla zaledwie 4 elementów liczba potrzebnych porównań wynosi 13 podczas, gdy nawet algorytm sortowania bąbelkowego wykonałby ich tylko 6. Algorytmowi zajmuje bardzo dużo czasu dodatkowa potrzeba na porównywanie elementów z zakresów, które się na siebie nakładają.

Złożoność

Przyjmuje się, że złożoność algorytmu wynosi O(n~2.71), a złożoność pamięciowa wynosi O(n). Wynika ona z faktu, że dla każdego wywołania funkcji istnieje potrzeba przechowywania danych na temat poprzedniego zakresu.

Implementacja

Przygotowanie sortowania algorytmem Komicznym nie jest trudne, ponieważ sortowanie odbywa się w sposób rekurencyjny i instrukcję sortowania wystarczy jedynie zapisać w wybranym języku programowania. Oto przykładowa implementacja, która sortuje dane zapisane w tablicy tab. Zmienne L i P oznaczają kolejny lewy i prawy indeks wybranego zakresu:

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

W każdym wywołaniu jeśli (2.) istnieje potrzeba zamiany skrajnych elementów to należy ją (3. - 7.) wykonać, a następnie (8.) jeśli istnieje możliwość podziału za 3 zakresy to (9. - 12.) należy posortować odpowiednie grupy zgodnie z podanym wcześniej algorytmem.

Dla wygody wywoływania funkcji sortuj() warto dopisać jej przeciążenie, które nie będzie wymagać zakresu:

C++
C#
  1. void sortuj(int* tab, int n) {
  2.   sortuj(tab, 0, n - 1);
  3. }

Testowanie funkcji

W celu przetestowania napisanej funkcji sortujące można skorzystać z poniższego fragmentu kodu, który wczyta rozmiar tablicy, jej elementy, a następnie wypisze posortowaną tablice.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj ile jest elementow\n n = ";
  4.   cin >> n;
  5.   int* tab = new int[n];
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   sortuj(tab, n);
  10.   cout << "Po posortowaniu:\n";
  11.   for (int i = 0; i < n; i++)
  12.     cout << tab[i] << " ";
  13.   system("pause");
  14.   return 0;
  15. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1