10.3 Merge Sort

1 Úvod 2 Grafy 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 10.1 Řazení 10.2 Základní řadící algoritmy 10.3 Merge Sort 10.4 QuickSelect 11 Dynamické programování Index Literatura

Poznámka 10.1 (Princip Merge Sortu)

Jedná se o rychlý rekurzivní algoritmus pro řazení, založený na slévání seřazených podposloupností.

Posloupnost o jednom prvku je už seřazená.

Mějme vstupní neseřazenou posloupnost $n$ prvků pro $n \ge 2$. Rozdělíme ji na dvě části poloviční délky (řekněme prvních $\lfloor n/2 \rfloor$ a zbývajících $\lceil n/2 \rceil$ prvků).

Rekurzivním voláním téhož algoritmu na obě poloviny je seřadíme.

Obě seřazené poloviny posléze slijeme dohromady do jedné seřazené posloupnosti a máme výsledek

\begin{algorithm}
\begin{algorithmic}
\STATE Pokud $n = 1$: vrať jako výsledek $b_1 = a_1$ a skonči
\STATE $x_1, ..., x_{\lfloor n/2 \rfloor}$: MergeSort($a_1, ..., a_{\lfloor n/2 \rfloor}$)
\STATE $y_1, ..., y_{\lfloor n/2 \rfloor}$: MergeSort($a_{\lfloor n/2 \rfloor + 1}, ... , a_n$)
\STATE Vrať $b_1, ..., b_n$ := Merge($x_1, ..., x_{\lfloor n/2 \rfloor}; y_1, ..., y_{\lfloor n/2 \rfloor}$)\end{algorithmic}
\end{algorithm}

Algoritmus 10.2: MergeSort

\begin{algorithm}
\begin{algorithmic}
\STATE $i := 1, j := 1, k := 1$
\WHILE { $i \le m$ a $j \le n$ }
    \IF { $x_i \le y_j$ }
        \STATE $z_k := x_i$
        \STATE $i := i + 1$
    \ELSE
        \STATE $z_k := y_j$
        \STATE $j := j + 1$
    \ENDIF
    \STATE $k := k + 1$
\ENDWHILE
\IF { $j \le m$ }
    \STATE $z_k,...,z_{m+n} := x_j,...,x_m$
\ENDIF
\IF { $j \le n$ }
    \STATE $z_k,...,z_{m+n} := y_j,...,y_n$
\ENDIF\end{algorithmic}
\end{algorithm}

Algoritmus 10.3: Merge

Pozorování 10.3

Operace Merge pouze přesouvá prvky a každý prvek přesune právě jednou.

Její časová složitost je tedy $\Theta (n+m)$, kde $n, m$ jsou délky slévaných polí.

Vyžaduje pomocnou paměť ve formě pomocného pole velikosti $\Theta (n + m)$

Věta 10.3 (Časová složitost `MergeSort`)

$\Theta (n \log n)$

Zobrazit důkaz

Rozdělení posloupnosti a slití seřazených kusů trvá čas $cn$.

Algoritmus volá $2×$ sebe sama na vstupy velikosti $n/2$. Proto

\begin{align*} T(1) &= 1 \\ T(n) &= 2 · T (n/2) + cn \\\end{align*}

Po rozvinutí dostaneme:

\begin{align*} T (n) &= 2 \cdot (2 \cdot T (n/4) + cn/2) + cn \\ &= 4 \cdot T (n/4) + 2cn \\ &= 8 \cdot T (n/8) + 3cn \\ &… \\ &= 2^k \cdot T (n/2^k) + kcn.\end{align*}

Rekurze skončí, když $n/2^k = 1$ čili $k = \log n$.

Tím dostaneme $T(n) = 2^{\log n} \cdot T(1) + \log n \cdot cn = Θ(n) + cn \log n = Θ(n \log n)$.

$\square$

Věta 10.4 (Paměťová složitost `MergeSort`)

$\Theta (n)$

Zobrazit důkaz

MergeSort si pamatuje lokální proměnné: vstup a jejich setříděné poloviny, dohromady $\Theta(n)$ paměti. Plus kontext pro návrat z rekurzivního zanoření ($O(1)$ paměti).

Mimo to obě rekurzivní volání spotřebují další paměť, ale jelikož vždy běží pouze jedno z nich, stačí započítat pouze jedno.

Dostaneme tuto rekurentní rovnici (pro kladnou konstantu d):

\begin{align*} M(1) &= 1,\\ M(n) &= dn + M(n/2)\\\end{align*}

To nám pro $M(n)$ dává geometrickou řadu $dn + dn/2 + dn/4 + ...$, která má součet $\Theta(n)$