10.2 Základní řadící algoritmy

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

10.2 Základní řadící algoritmy

10.2.1 SelectSort a InsertSort

Vstupní posloupnost se rozdělí na levou seřazenou a pravou neseřazenou část.

Na počátku je levá část prázdná a pravá část je celá vstupní posloupnost.

Po vložení prvku se hranice mezi seřazenou a neseřazenou částí posune o jednu pozici doprava.

Definice 10.2 (`SelectSort`)

Z neseřazené pravé části se vybere minimum a prohodí se s jejím prvním prvkem, tj. přímo za seřazenou část.

Invariant: Po $i$-té iteraci je vlevo seřazená posloupnost délky $i$ a vpravo zbývá $n − i$ neseřazených prvků, které jsou $\geq$ než čísla v levé části.

Pozorování 10.1

Algoritmus SelectSort seřadí $n$-prvkové pole v čase $\Theta(n^2)$ a je in-place, nestabilní, datově necitlivý.

Definice 10.3 (`InsertSort`)

Z neseřazené pravé části se vezme první prvek a vloží se zprava na správnou pozici v levé seřazené části.

Invariant: Po $i$-té iteraci je vlevo seřazená posloupnost délky $i + 1$ a vpravo zbývá $n − 1 − i$ neseřazených prvků.

Pozorování 10.2

Algoritmus InsertSort seřadí $n$-prvkové pole v čase $O(n^2)$ a je in-place, stabilní, datově citlivý.

10.2.2 Algoritmus BubbleSort

Řazení probubláváním větších prvků doprava.

Postupně zleva doprava se porovnávají dvojice sousedních prvků a pokud jsou prvky dvojice v nesprávném pořadí, prohodí se.

Po prvním průchodu bubliny se největší prvek dostane na poslední místo.

Celý postup se opakuje nejvýše ($n − 1$)-krát: pokaždé se seřazená podposloupnost vpravo prodlouží o jednu pozici doleva.

Pokud se během jednoho průchodu neprohodila žádná dvojice sousedů, už se nikdy žádná neprohodí a řazení skončilo.

Vhodný algoritmus, pokud je např. vstupní posloupnost z velké části seřazená.

\begin{algorithm}
\begin{algorithmic}
\STATE end := n
\STATE zmena := 1
\WHILE { zmena = 1 }
  \STATE zmena := 0
  \FOR { j := 1 $\dots$ (end − 1) }
    \IF { P[j] > P[j + 1] }
      \STATE prohoď P[j] a P[j + 1]
      \STATE zmena := 1
    \ENDIF
  \ENDFOR
  \STATE end − −
\ENDWHILE\end{algorithmic}
\end{algorithm}

Algoritmus 10.1: BubbleSort

Věta 10.1

Algoritmus BubbleSort korektně seřadí $n$-prvkové pole.

Invariant: nejpozději po $i$-té iteraci cyklu na řádcích (3)–(9) se $i$ největších prvků pole nachází seřazeno na $i$ posledních pozicích zprava.

Zobrazit důkaz

IZ: Invariant platí pro $i = 1$. Po $1$.iteraci je největší prvek celé posloupnosti zaručeně na poslední pozici.

IK: Předpokládejme, že Invariant platí pro všechna $j < i$ a tedy $i − 1$ největších prvků se nachází seřazeno na posledních $i − 1$ pozicích vpravo. Proveďme $i$-tou iteraci.

Tím probublá největší hodnota levého zbytku doprava, levá část se zkrátí o jedna a pravá seřazená část se zvětší o jeden prvek, a invariant platí.

$\square$

Věta 10.2

BubbleSort seřadí $n$-prvkové pole v čase $O(n^2)$ a je in-place, stabilní, datově citlivý.

Zobrazit důkaz

Iterací je nejvýše $n − 1$, $i$-tá iterace trvá $\Theta(n − i)$ kroků, což dává časovou složitost $O(n^2)$.

Kromě vstupního pole potřebuje pouze $O(1)$ paměti. Je stabilní, neboť podmínka na řádku (6) zabrání prohození stejných prvků.

Je datově citlivý, neboť končí, jakmile nedošlo během některé iterace ke změně. V nejlepším případě již seřazeného pole má složitost $\Theta(n)$.

$\square$