Jedním z nejdůležitějších požadavků při třídění polí je úsporné využívání operační paměti počítače. To znamená, že bychom měli pracovat "na místě", přímo uvnitř tříděného pole, aniž bychom deklarovali pole pomocné. Jinými slovy výchozí (zdrojová) posloupnost musí být uložena na stejném místě paměti jako posloupnost cílová.

Má-li tříděné pole n prvků, měli bychom tedy spotřebu paměti vyjádřit číslem n+c, kde c je malá konstanta.

Dalším požadavkem je samozřejmě efektivita algoritmu. Vhodným měřítkem efektivity může být počet porovnání klíčů a počet přesunů prvků v poli. Obvykle je významnější počet přesunů, neboť bývají časově náročnější. Existují ale i příklady, ve kterých je porovnání složitější než přesun dat. Při našich úvahách si budeme všímat závislosti obou těchto veličin na počtu prvků n tříděného pole.

Velmi jednoduché algoritmy pro třídění vyžadují řádově n² operací a jsou vhodné pro malé objemy tříděných dat. Navíc se na nich snadno demonstrují principy třídění.

Kvalitní algoritmy pro třídění polí vyžadují řádově n.log n porovnání, tedy podstatně méně. Jednotlivé operace mohou ale být složitější, takže pro malá n mohou být výhodnější metody jednoduché.

V následujících odstavcích budeme zpravidla předpokládat, že tříděná posloupnost je uložena v poli a, deklarovaném příkazem

var a: array [1..n] of data;

V některých případech toto pole doplníme zleva o několik prvků, které poslouží jako zarážky. Vedle toho budeme předpokládat deklaraci typu index:

type index = 1..n

Zpět

Poslední aktualizace: 29-05-2003.