|
|
|
Pod pojmem třídění budeme rozumět uspořádání zadané posloupnosti dat podle určitého klíče v neklesajícím nebo nerostoucím pořadí. Prvky
posloupnosti, kterou třídíme, mohou být jakéhokoli typu, samozřejmě
všechny stejného. Obecně půjde o záznamy (struktury); klíčem,
podle kterého budeme prvky posloupnosti porovnávat, může být buď přímo
některá ze složek tohoto záznamu nebo funkce, vypočítaná na základě
celého záznamu. My budeme pro jednoduchost předpokládat, že každý z
prvků posloupnosti obsahuje numerickou složku jménem klíč.
Občas budeme pro stručnost mluvit pouze o porovnávání prvků;
budeme tím ovšem mít na mysli porovnávání jejich klíčů. Podobně
budeme-li hovořit o "nejmenším prvku", budeme mít na mysli
prvek s nejmenším klíčem atd. Při
výkladu metod třídění budeme rozlišovat dvě základní
situace: a) Jestliže známe předem počet prvků
posloupnosti a všechny prvky tříděné posloupnosti jsou uloženy ve
vnitřní paměti počítače, kde k nim můžeme přistupovat
v libovolném pořadí (tedy třídíme data, uložená v poli), hovoříme
o vnitřním třídění
. b) Jestliže počet prvků tříděné posloupnosti předem neznáme a prvky tříděné posloupnosti jsou uloženy ve vnější paměti se sekvenčním přístupem (tedy třídíme soubor na magnetické pásce nebo disku), hovoříme o vnějším třídění
|
|
|
