Vnitřní třídění
Vnitřní třídění je (oproti
vnějšímu) třídění prvků pole v operační paměti, nikoli v souboru.
Různé algoritmy pro třídění dle přednášky 5. ledna 2006:
Složitost úlohy
Tvrzení: Úloha vnitřního třídění
založeného na porovnávání dvou prvků má (časovou) složitost
n log
n.
Důkaz: Větší určitě nemá (viz
Heap Sort). Mějme strom výpočtu (strom všech provedených operací), který se podle pořadí daných dat větví při porovnáních. Takový strom má
n! listů, výška je tedy aspoň log(
n!) a to se dá odhadnout (prý) jako
n log
n.
