|
Tyto metody se zabývají tříděním sekvenčních souborů. Připomeňme se nejdůležitější rozdíly ve srovnání s metodami pro třídění polí. O
souboru předpokládáme, že je uložen na vnějším, zpravidla
magnetickém médiu se sekvenčním přístupem. To znamená, že musíme
zpracovávat jeden záznam po druhém v pořadí, v jakém jsou v
souboru uloženy. Vedle
toho zde předem neznáme rozsah tříděných dat, tj. počet n
záznamů v souboru
. Lze ale předpokládat, že je tak velký,
že se soubor nevejde do operační paměti počítače. Čtení
záznamu ze souboru nebo uložení (zápis) do souboru budeme společně
označovat jako přístup do
souboru.
Přístup do souboru trvá o několik
řádů déle než porovnávání záznamů, takže je z hlediska
efektivity algoritmů pro vnější třídění rozhodující.
Proto si při rozboru algoritmů pro vnější třídění
budeme všímat jen počtu přístupů do souboru. Na
druhé straně máme obvykle k dispozici dostatečné množství vnější
paměti, takže s ní nemusíme příliš šetřit a budeme při
třídění využívat pomocných souborů.
|
|