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:

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

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

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

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:

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.

1. double* L_pom;

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

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

• Kod źródłowy Implementacja

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

• Kod źródłowy Zadanie 1