Strona główna » Algorytmy » Sortowanie » Sortowanie Przez Scalanie
 

Sortowanie Przez Scalanie

O sortowaniu

Sortowanie przez scalanie to obecnie najszybsza znana metoda sortowania danych. Działanie algorytmu opiera się na scalaniu posortowanych już list. W ten sposób zaoszczędzamy porównania - co za tym idzie czas. Posortowane listy uzyskujemy dzieląc listę elementów na pary elementów (możliwe jest wystąpienie elementu bez pary), które sortujemy w obrębie ich pod listy.

Przykład

Weźmy na początek listę L:={3, 5, 2, 4, 1}. Algorytm na początek musi podzielić listę na mniejsze podlisty o maksymalnie dwóch elementach. Kolejne kroki rozbijania przedstawia poniższa tabelka:

KrokPodlisty
1{3, 5, 2, 4, 1}
2{3, 5, 2}, {4, 1}
3{3, 5}, {2}, {4, 1}

Kolejny krok polega na posortowaniu każdej z powstałych podlist. Innymi słowy uzyskujemy {3, 5}, {2}, {1, 4}. Teraz przechodzimy do części drugiej działania algorytmu - scalania. Na tym etapie mamy zagwarantowane, że scalane listy są już posortowane. Innymi słowy możemy porównać pierwsze elementy scalanych list. Dopisać na listę wynikową mniejszą liczbę i usunąć ze starej listy. Powtarzając krok porównywania dojdziemy do momentu, gdy nie będziemy mieć elementów do porównania - wtedy przepisujemy wszystkie pozostałe elementy do listy wynikowej z niepustej listy. W ten sposób uzyskujemy posortowaną listę.

Żeby lepiej to zrozumieć zobaczmy kolejne kroki scalania listy {3, 5} oraz {2}:

KrokWynikLista 1Lista 2Komentarz
1{}{3, 5}{2}2 < 3, dopisujemy 2 do wyniku i usuwamy z Lista 2
2{2}{3, 5}{}nie możemy porównać, przepisujemy pozostałe elementy z Lista 1 do wyniku
3{2, 3, 5}{}{}obie listy puste, scalanie zakończone

Zostały już nam teraz dwie listy do scalanie {2, 3, 5}, {1, 4}:

KrokWynikLista 1Lista 2Komentarz
1{}{2, 3, 5}{1, 4}1 < 2, dopisujemy 1 do wyniku i usuwamy z Lista 2
2{1}{2, 3, 5}{4}4 > 2, dopisujemy 2 do wyniku i usuwamy z Lista 1
3{1, 2}{3, 5}{4}4 > 3, dopisujemy 3 do wyniku i usuwamy z Lista 1
4{1, 2, 3}{5}{4}4 < 5, dopisujemy 4 do wyniku i usuwamy z Lista 2
5{1, 2, 3, 4}{5}{}nie możemy porównać, przepisujemy pozostałe elementy z Lista 1 do wyniku
6{1, 2, 3, 4, 5}{}{}obie listy puste, scalanie zakończone

W ten sposób uzyskaliśmy posortowaną listę L:={1, 2, 3, 4, 5}.

Złożoność

Działanie takiego algorytmu ma złożoność czasową O(nlogn). Jest to zaleta ograniczenia operacji porównania. Dane porównujemy dopiero przy scalaniu. Dla dwóch list o długościach a i b wykonamy maksymalnie a + b - 1 porównań. W pierwszym etapie scalania mamy n/2 par, w kolejnym n/4, ... aż uzyskamy tylko dwie listy. W pierwszym mamy do wykonania jedną, drugim dwie i w ostatnim maksymalnie n/2 porównań. W przypadku złożoności pamięciowej to potrzebujemy dodatkowej tablicy długości n do przechowywania posortowanych wyników. W ten sposób uzyskujemy złożoność rzędu O(n).

Implementacja

Przed rozpoczęciem pisania funkcji sortującej warto napisać funkcję scalającą. Kiedy będziemy pewni jej niezawodności nie powinniśmy mieć z nią problemów później:

Funkcja nie zwraca nic i przyjmuje cztery argumenty: L - lista do posortowania, from, sr, to - kolejno indeksy elementów od którego, środkowy indeks listy oraz do którego indeksu wykonujemy sortowanie. Wewnątrz funkcji korzystamy ze zmiennej globalnej L_pom, która przechowuje częściowo posortowaną listę. Jest to bufor, który wpływa na złożoność pamięciową rzędu O(n).

C++
C#
  1. void scal(double* L, int from, int sr, int to) {
  2.   for (int i = from; i <= to; i++)
  3.     L_pom[i] = L[i];
  4.   int i = from, j = sr + 1;
  5.   for (int k = from; k <= to; k++) {
  6.     if (i <= sr) {
  7.       if (j <= to) {
  8.         L[k] = (L_pom[j] < L_pom[i]) ? L_pom[j++] : L_pom[i++];
  9.       } else {
  10.         L[k] = L_pom[i++];
  11.       }
  12.     } else {
  13.       L[k] = L_pom[j++];
  14.     }
  15.   }
  16. }

(1.) Na początek ustalamy indeksy elementów początkowych dwóch podlist: i / j to indeks początkowego elementu listy 1 / listy 2. (2.) Ze względu na to, że będziemy zapisywać posortowane dane w głównej tablicy L to (3.) wykonujemy kopię elementów w tablicy L_pom. Nasz kolejny krok polega na właściwym scaleniu tablic. (4.) Sprawdzamy czy pierwsza podlista ma jakiekolwiek elementy. Jeśli nie to (13.) przepisujemy element z listy 2. Jednak jeśli pierwsza lista nie jest pusta to (7.) sprawdzamy czy druga ma. Analogicznie jeśli nie ma to (10.) przepisujemy element z listy 1. (8.) Jednak, gdy obie listy są niepuste to porównujemy i przepisujemy mniejszy element (w przypadku sortowania rosnąco). W ten sposób uzyskujemy funkcją scalającą.

Kolejnym etapem jest napisanie funkcji nadrzędnej sortuj(), która będzie zarządzać utworzeniem podlist i ich scaleniem:

C++
C#
  1. void sortuj(double* L, int from, int to) {
  2.   if (to <= from)
  3.     return;
  4.   int sr = (to + from) / 2;
  5.   sortuj(L, from, sr);
  6.   sortuj(L, sr + 1, to);
  7.   scal(L, from, sr, to);
  8. }

(1.) Funkcja nie zwraca nic - sortujemy w miejscu. Jako argumenty przyjmujemy L - listę elementów, from, to zakresy indeksów od którego do którego sortujemy. (2.) Jeśli zakresy from i to są równe oznacza to, że chcemy sortować pojedynczy element, dlatego (3.) dalej nie dzielimy zakresu. (4.) Wyliczamy elementy środkowy zakresu. Sortujemy listę w zakresie [from, sr] (5.) oraz (6.) [sr, to]. Na koniec (7.) obydwie posortowane podlisty scalamy.

Testowanie funkcji

W implementacji należy pamiętać, że potrzebujemy zmiennej globalnej L_pom, którą deklarujemy jako zmienną globalną. Potrzebujemy mieć do tego miejsca dostęp podczas każdego wywołania rekurencji.

C++
C#
  1. double* L_pom;

Główna funkcja main() wczyta dane i utworzy listę pomocniczą L_pom:

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

Zadania

Zadanie 1

Napisz program, który wykorzystując Sortowanie przez scalanie posortuje malejąco listę liczb całkowitych i wypisze ją na ekran.

Przykładowo dla listy [7 3 6 4 2] program wypisze na ekran:

  1. 7 6 4 3 2