BPC-ALD - Skripta_rev2019_2
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.
2
r
v
= ).
Vnější třídění je založeno na operaci zatřiďování. Při ní je z více setříděných sekvencí vytvářena
jedna delší setříděná sekvence. Setříděným sekvencím budeme říkat běhy. Na začátku třídění
běhy mají délku 1, jsou tvořeny jedním prvkem. Opakovaným procesem zatřiďování jsou z nich
vytvářeny stále delší a delší běhy, až se dosáhne stavu, že je vytvořen běh tak dlouhý, že
obsahuje všechny tříděné prvky. Tím třídění končí.
Popis algoritmu
Proces třídění má dvě fáze – rozdělování a zatřiďování.
Fáze 1 – rozdělování
První fáze je poměrně rychlá. Jejím cílem je pravidelně rozdělit tříděné prvky do v souborů,
abychom mohli zahájit vlastní třídící proces. Vezmeme ze stanoveného počtu r souborů
polovinu (v) a otevřeme je pro výstup (zápis). Do nich pravidelně rozděluje tříděné prvky. První
prvek zapíšeme do prvního souboru, druhý prvek do druhého souboru, …, až v-tý prvek do v-
tého souboru, následující prvek opět do prvního souboru atd.
Tedy tříděné prvky
n
a
a
a
a
,...,
,
,
3
2
1
rozdělíme do souborů následovně
1. soubor:
,...
,
,
1
2
1
1
+
∗
+
v
v
a
a
a
2. soubor:
,...
,
,
2
2
2
2
+
∗
+
v
v
a
a
a
….
v-tý soubor:
,...
,
,
3
2
v
v
v
a
a
a
∗
∗
Vnější třídění je
určeno pro velké
objemy dat.
vstupních
− 51 −
Po dokončení rozdělování soubory výstupní soubory uzavřeme a následně je otevřeme jako
vstupní (pro čtení) a zbývající polovinu souborů otevřeme jako výstupní. Délku běhů nastavíme
na 1.
Fáze 2 - zatřiďování
Ze všech v vstupních souborů načteme jejich první běh, zatříděním z něho vytvoříme jeden delší
výstupní běh a ten uložíme do prvního výstupního souboru. Pak ze vstupních souborů načteme
druhý běh, z něho opět vytvoříme výstupní běh a uložíme ho do druhého výstupního souboru. A
tak pokračujeme až v-tý vytvořený výstupní běh uložíme do v-tého souboru, následující (v+1)-tý
vytvořený výstupní běh uložíme opět do prvního souboru atd. Tj. vytvářené výstupní běhy
pravidelně rozdělujeme do v výstupních souborů.