12-Trideni_vnejsi
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
BPC-ALD
12. přednáška
Vnější třídění se stejným počtem vstupních a výstupních souborů,
odvození složitost algoritmu. Vnější třídění s využitím vnitřního třídění,
odvození složitosti.
rev. 2019.2
Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz)
Vnější třídění
Vnější třídění
• Během třídění jsou tříděné prvky uloženy v souborech ve vnější
paměti (disku).
• Tříděné prvky jsou po malých skupinách přeneseny do operační
paměti, v ní jsou zatřiďovány a pak opět ukládány do souborů.
• Operace čtení a zápis ze resp. do souboru jsou ve srovnání s
operacemi přesunu prvků v operační paměti výrazně pomalejší.
• Vnější třídění je proto pomalejší než vnitřní třídění.
• Používáme ho pouze tehdy, když třídíme tak velké množství prvků, že
je nelze všechny současně umístit do operační paměti.
Třídění se stejným počtem vstupních a
výstupních souborů
• Máme 𝑣 vstupních souborů a stejný počet výstupních souborů.
• Vstupní soubory obsahují setříděné posloupnosti - tzv. běhy.
• Délka běhu je v prvním kroku 1 prvek, ve druhém kroku 𝑣 prvků, ve
třetím kroku 𝑣2prvků atd.
• Vnější třídění je založeno na operaci zatřiďování.
• Z více setříděných sekvencí je vždy vytvořena jedna delší setříděná sekvence.
• Algoritmus probíhá ve dvou fázích:
1. Rozdělování
2. Zatřiďování
Třídění se stejným počtem vstupních a
výstupních souborů
• Fáze rozdělování
• Tříděné prvky budeme rovnoměrně rozdělovat do 𝑣 výstupních souborů.
Třídění se stejným počtem vstupních a
výstupních souborů - fáze rozdělování
• Otevřeme 𝑣 souborů pro zápis.
• První prvek uložíme do prvního souboru, druhý prvek do druhého
souboru, ... 𝑣-tý prvek do 𝑣-tého souboru. Následující prvek opět do
prvního souboru atd.