|
O mojí osobě
Něco ke stažení Články a návody Poezie Odkazy |
Merge sort Algoritmus mergesort pracuje vždy v čase O(n*log n), což je také nejlepší možný asymptotický čas pro obecnou úlohu třídění n prvků. Stejně jako algoritmus Quick sort používá pro třídění metodu rozděl a panuj. Pokud dostane na vstupu pole o délce větší než 1 prvek, rozdělí ho na dvě menší a rekurzivně je setřídí. Dvě výsledná pole poté slije dohromady a odevzdá je na výstupu. Pokud je vstupní pole 1 znak, jedná se o setříděné pole a rovnou je vráceno na výstupu. Časová složitost je zřejmá z postupu. Výška stromu rekurze je logaritmus n o základu 2 (pole dělíme vždy na poloviny) a v každém kroku provedeme slévání dvou setříděných seznamů (to umíme v lineárním čase). Výsledná složitost je tedy O(n*log n). Funkce MergeSort utřídí položky pole P o indexech l až r. Pomocne je pomocné pole o velikosti odpovídající poli P. Setřídění celého pole P pak zařídí volání MergeSort(P, pomocne, 1, n).
void MergeSort (int *P, int *pomocne,int l,int r)
{
int x;
if (l < r)
{
x= (l + r) / 2;
MergeSort(P,pomocne, l, x);
MergeSort(P,pomocne, x+1, r);
Merge(P, pomocne, l, x, r);
};
return;
};
void Merge(int *P, int *pomocne, int l, int x, int r)
/*
provede slití úseků P[l..x] a P[x+1..r] pomocí pole pomocne
*/
{
int i,j;
int k;
for (i=l; i < r+1; i++ ) pomocne[i]=P[i];
k=l;
i=l; j=x+1;
while (k < r)
{
if (i > x)
{
P[k]=pomocne[j];
j++;
}
else if (j > r)
{
P[k]=pomocne[i];
i++;
}
else if pomocne[i]>pomocne[j]
{
P[k]=pomocne[j];
j++;
}
else
{
P[k]=pomocne[i];
i++;
};
k++;
};
};
|