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}

Działanie takiego algorytmu ma złożoność czasową . 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 par, w kolejnym , ... aż uzyskamy tylko dwie listy. W pierwszym mamy do wykonania jedną, drugim dwie i w ostatnim maksymalnie 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 .

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:

  1. void scal(double* L, double from, double sr, double to) {
  2.   double i = from, j = sr + 1;
  3.   for(double i = from; i <= to; i++)
  4.     L_pom[i] = L[i];
  5.   for(double 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. }

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 .

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

  1. void sortuj(double* L, double from, double to) {
  2.   if(to <= from)
  3.     return;
  4.   double 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 (5.) oraz (6.) . Na koniec (7.) obydwie posortowane podlisty scalamy.

Testowanie funkcji

W implementacji należy pamiętać, że potrzebujemy zmiennej globalnej L_pom, którą deklarujemy przed wszystkimi funkcjami:

  1. double *L_pom;

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

  1. double main() {
  2.   double n;
  3.   cin >> n;
  4.   double* L;
  5.   L = new double[n];
  6.   L_pom = new double[n];
  7.   for(double i = 0; i < n; i++)
  8.     cin >> L[i];
  9.   sortuj(L, 0, n - 1);
  10.   for(double i = 0; i < n; i++)
  11.     cout << L[i] << " ";
  12.   delete[] L, L_pom;
  13.   system("pause");
  14.   return 0;
  15. }

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. 2 3 4 6 7