Sortowanie (Mergesort)

Question

Witam,czy mógłbym mi ktoś troche rozjaśnić ten algorytm:http://www.algorytm.org/algorytmy-sortowania/sortowanie-przez-scalanie-mergesort/merge-j.html

analizuję go i nie mogę dojść do ładu i składu.Np.dlaczego te metoda przyjmuję takie wartości:

private static void merge(int pocz, int sr, int kon)

Co to w ogóle jest : pocz,sr,kon?

tab[q++]=t[j++];

Co tutaj wyżej się dzieje?

Czytałem już sporo na temat sortowanie przez scalanie,ale na przykładzie tej implementacji tego algorytmu nie mogę mimo wszystko tego ogarnąć.

Answer 1

Algorytm ten ma dwie funkcje mergesort oraz merge (z ang. łączyć). Jak myślę że już dobrze wiesz algorytm ten działa na zasadzie dzielenia tablicy na mniejsze część, następnie posortowaniu ich a na końcu ponownym scaleniu. Spójrz na te fragment:

/* Procedura sortowania tab[pocz...kon] */
public static void mergesort(int pocz, int kon)
{
int sr;
if (pocz<kon) {
sr=(pocz+kon)/2;
mergesort(pocz, sr);    // Dzielenie lewej części
mergesort(sr+1, kon);   // Dzielenie prawej części
merge(pocz, sr, kon);   // Łączenie części lewej i prawej
}
}   

Jest to główny algorytm sortujący, wywołując go jako pocz i kon mamy kolejno początek tablicy czyli 0 a następnie n-1 czyli index ostatniego elementu. Kolejnym etapem jest tutaj znalezienie środka tablicy który zostaje przypisany do zmiennej sr i jak można zauważyć wykorzystywany w kolejnych wywołaniach mergesort. W skrócie mergesort wywołuje siebie samego dzieląc tablicę aż do momentu kiedy składa się ona z pojedynczych elementów (algorytm rekurencyjny). Kiedy już nastąpi podziała na najmniejsze części następuje ich scalanie oraz sortowanie, czyli następuje wywołanie funkcji merge która jako argumenty otrzymuje początek i koniec tabeli oraz dodatkowo środek czyli miejsce w którym nastąpił podział.

/* Scalanie dwoch posortowanych ciagow
tab[pocz...sr] i tab[sr+1...kon] i
wynik zapisuje w tab[pocz...kon] */
private static void merge(int pocz, int sr, int kon)
{
int i,j,q;
for (i=pocz; i<=kon; i++) t[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
i=pocz; j=sr+1; q=pocz;                 // Ustawienie wskaźników tablic
while (i<=sr && j<=kon) {         // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
if (t[i]<t[j])
tab[q++]=t[i++];
else
tab[q++]=t[j++];
}
while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
}

Tutaj z pomocniczej tabeli do której wysłaliśmy elementy przekładamy je do naszej wynikowej tabeli już w odpowiedniej kolejności. Odnośnie

tab[q++]=t[i++];

Ta linijka działa na zasadzie wpisz w miejsce tab[q] wartość spod t[i] a następnie zwiększ "q" oraz "i" o jeden. Gdyby wyglądało to w ten sposób:

tab[++q]=t[++i];

Najpierw zwiększylibyśmy wartości "q" oraz "i" o jeden a dopiero po tym wykonalibyśmy operację przypisania.

Comments

Elegancko wytłumaczone! :)

Answer 2

* (int pocz, int sr, int kon) - są to argumenty metod.

Co to w ogóle jest : pocz,sr,kon?

- nie rozumiem .... są to nazwy tych argumentów, zmiennych lokalnych. - o to chodziło ? ;p

Co tutaj wyżej się dzieje?

- "++" służy do zwiększania wartości o 1.

"tab" i "t"- nazwy tablic

"q++" i "j++" zostaje użyte jako numer komórki w tablicy do której się odwołuje. :)

Więc do pewnej komórki w tablicy zostaje przypisana wartość innej komórki z innej tablicy ;)