Pewnego wykładu profesor prowadzący
zajęcia z informatyki powiedział: "każdy szanujący się informatyk powinien
posiadać w swym portfolio porządny algorytm do sortowania”. Przez porządny,
rozumiemy taki który, w najkrótszym możliwym czasie i przy użyciu najmniejszej
ilości zasobów wyprodukuje na wyjściu poukładany ciąg elementów.
Do tej grupy algorytmów zalicza się
sortowanie przez scalanie (ang. merge sort). Bazuje ono na zasadzie "dziel
i rządź" - czyli na podzieleniu problemu na mniejsze części, co znacznie
ułatwia ich rozwiązywanie.
Sortowanie przez scalanie polega na
sukcesywnym połowieniu szeregu danych wejściowych do momentu pozostania z
jednym elementem w zbiorze. Taki zbiór, ze względu na jego liczebność, bez wahania
możemy nazwać posortowanym. Następnym krokiem jest scalenie takich jednoelementowych
zbiorów w jeden, większy. Zgodnie z tą regułą "cofamy się", aż
wszystkie takie podzbiory scalimy w całość, uzyskując posortowany ciąg
wejściowy.
Ceną, jaką musimy zapłacić za prostotę
i szybkość jest dodatkowa pamięć którą zużywa algorytm. Pamięć ta jest używana
jako tymczasowy bufor przy scalaniu poszczególnych fragmentów ciągu elementów.
Działanie algorytmu przedstawione jest
na rysunku poniżej, co znacznie ułatwia zrozumienie sposobu jego działania.
Implementacja
Najelegantszy, a zarazem najbardziej
czytelny sposób implementacji tego algorytmu uzyskamy za pomocą rekurencji -
czyli funkcji wywołującej samą siebie. Główna pętla programu prezentuje się w
następujący sposób:
void mergeSort(int[] arr, int p, int q)
{
if (p >= q)
{
return;
}
int r = (p +
q) / 2;
mergeSort(arr, p, r);
mergeSort(arr, r + 1, q);
merge(arr, p, r, q);
}
Gdzie argumenty funkcji oznaczają
odpowiednio: tablicę elementów które mają zostać posortowane, indeks elementu pierwszego
ciągu, indeks ostatniego elementu ciągu. Funkcja wyznacza środek ciągu r i następnie wywołuje samą siebie
dzieląc wirtualnie tablicę na mniejsze. Instrukcja warunkowa if czuwa nad ilością elementów i jeżeli
w ciągu znajduje się jeden element zakańcza ona rekursywne wywołania.
Najważniejszą częścią jest
implementacja funkcji scalania, która znajduje się na listingu poniżej:
void merge(int[] a, int p, int r, int q)
{
int[]
tmp = new int[q
- p + 1];
int
i = p, j = r + 1, k = 0;
while
(i < r+1 && j < q+1)
{
if
(a[i] <= a[j])
{
tmp[k] = a[i];
i++;
}
else
{
tmp[k] = a[j];
j++;
}
k++;
}
if
(i >= r+1)
{
while
(j < q+1)
{
tmp[k] = a[j];
j++;
k++;
}
}
else
{
while
(i < r+1)
{
tmp[k] = a[i];
i++;
k++;
}
}
k = 0;
for
(i = p; i < q+1; i++)
{
a[i] = tmp[k];
k++;
}
}
}
Argumenty tej funkcji to: tablica z
sortowanymi elementami, indeks pierwszego elementu pierwszej (lewej) tablicy,
koniec pierwszej (lewej) tablicy oraz koniec drugiej (prawej) tablicy. Tablica
prawa zaczyna się od elementu o indeksie r+1.
Działanie funkcji przedstawia się następująco: najpierw jest tworzony bufor w
którym będą przetrzymywane elementy oraz inicjowane są indeksy do elementów.
Pierwsza pętla scala prawą i lewą część ciągu aż do momentu osiągnięcia końca
jednego z nich. Instrukcja if(i >=
r+1) ocenia który z ciągów już w całości przepisano a który jeszcze trzeba
przepisać do bufora. Po skończeniu scalania bufor jest przepisywany do tablicy
wejściowej.
Podsumowanie
Niewątpliwą zaletą sortowania przez
scalanie jest jego szybkość i łatwość w implementacji. Złożoność obliczeniowa tego
algorytmu to N*log(N) gdzie N oznacza
liczbę elementów i jest ona niezależna od danych wejściowych tzn. niezależnie
jaki ciąg danych pojawi się na wejściu czas obliczeń będzie zawsze równy N*log(N). Inaczej jest w przypadku
konkurencyjnego rozwiązania - sortowania szybkiego którego złożoność waha się
od N*log(N) do N2.
Brak komentarzy:
Prześlij komentarz