Externí řazení

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í:

1. Přirozené řazení (metoda přirozeného sloučení)
2. Obousměrné vyvážené řazení
   1. Řazení podle n-way merge.
3. Vícefázové řazení (Fibonacci)

Literatura

• Richard Forsyth. Pascal pro všechny = Pascal at Work and Play. Úvod do počítačového programování v Pascalu. - M .: Mashinostroenie, 1986. - 288 s.
• Robert Sedgwick. Základní algoritmy v C. Základy/Datové struktury/Řazení/Vyhledávání. - Petrohrad. : DiaSoftYUP, 2003. - 672 s. — ISBN 5-93772-081-4 .

• Niklaus Wirth. Algoritmy a datové struktury. Nová verze pro Oberon. - M. : DMK Press, 2012. - 272 s. - ISBN 978-5-94074-734-5 .