Externí třídicí - třídicí data umístěná na periferních zařízeních a nevejdou se do paměti RAM , to znamená, když nelze použít některý z interních řazení . Stojí za zmínku, že interní třídění je mnohem efektivnější než externí třídění, protože přístup k RAM trvá mnohem méně času než magnetické disky , pásky atd.
Nejčastěji se v DBMS používá externí třídění . Hlavním konceptem při použití externího třídění je koncept segmentu. Segment délky je posloupnost položek , ,…, ve které jsou všechny položky seřazeny podle nějakého klíče. Maximální počet segmentů v souboru (všechny prvky nejsou seřazeny). Minimální počet segmentů je 1 (všechny prvky jsou objednány).
Například v některém souboru A je jednorozměrné pole:
12 35 65 0 24 36 3 5 84 90 6 2 30
Rozdělme pole na segmenty:
12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30
Můžeme říci, že pole v souboru A se skládá z 5 segmentů.
Například v některém souboru B je jednorozměrné pole:
1 2 3 4 5 6 7 8 9 10
Rozdělme pole na segmenty:
| 1 2 3 4 5 6 7 8 9 10 |
Můžeme říci, že pole v souboru B se skládá z 1 segmentu.
Například v některém souboru A je jednorozměrné pole:
20 17 16 14 13 10 9 8 6 4 3 2 0
Rozdělme pole na segmenty:
| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |
Můžeme říci, že pole v souboru A se skládá ze 13 segmentů.
Myšlenkou většiny metod je rozdělit data do řady sekvencí, které se vejdou do paměti RAM. Dále je aplikována jedna z metod vnitřního třídění, po které jsou sekvence sloučeny. Čím větší je množství paměti RAM, tím delší budou sekvence, a tím menší bude jejich počet, což zvýší rychlost třídění.
Pokud je velikost paměti RAM malá, můžete rozdělit zdrojová data do několika sekvencí a poté přímo použít slučovací proceduru.
Základní způsoby třídění:
Algoritmy řazení | |
---|---|
Teorie | Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí |
Výměna | |
Výběr | |
Vložky | |
fúze | |
Žádné srovnání | |
hybridní | |
jiný | |
nepraktický |