Řazení (třídění)

Seřazení $N$ čísel podle velikosti - proces řádu složitosti $\sim N \log_2 N$.
Zopakovat $N$-krát proces vyhledání intervalu přímo nelze.

Malý počet čísel lze seřadit i algoritmem řádu $\sim N^2$ s malou multiplikativní konstantou.

Ukážeme následující algoritmy

• Přímé vkládání - složitost $\sim N^2\ \ (\rightarrow N \mbox{$\stackrel{<}{\sim}$}50)$
• Shellova metoda - složitost $\sim N^{\frac{3}{2}}$ (pro náhodná čísla $\sim N^{1.27}$)
  $(\rightarrow 50 \mbox{$\stackrel{<}{\sim}$}N \mbox{$\stackrel{<}{\sim}$}1000)$
• Heapsort - složitost $\sim N \log_2 N\ \ (\rightarrow N \mbox{$\stackrel{<}{\sim}$}50)$
  Názorný algoritmus, nepotřebuje žádnou paměť navíc. Nejhorší případ je jen asi o 20 % pomalejší než průměrná rychlost.
• Quicksort - složitost $\sim N^2$ - nejhorší případ (pro náhodná čísla $\sim N \log_2 N)$
  náhodná $N \mbox{$\stackrel{>}{\sim}$}1000$ - nejrychlejší známý - 1.5 až 2-krát rychlejší než Heapsort. Ovšem v nejhorším případě (pro správně seřazená čísla) má Quicksort složitost $\sim N^2$.