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.
Potřeba setřídit údaje se v praxi objevuje velmi často. Proto algoritmy pro třídění patří do
skupiny základních, velmi používaných algoritmů. Úloha třídění spočívá v seřazení prvků
datové množiny vzestupně podle jejich velikosti. Máme tedy n prvků dat
n
a
a
a
...
,
,
2
1
a předpokládáme, že jsou takového datového typu, u kterého je definováno srovnání dle
velikosti. Úkolem je prvky seřadit do posloupnosti
n
i
i
i
a
a
a
...
,
,
2
1
tak, že platí
n
i
i
i
a
a
a
≤
≤
≤
...
2
1
Můžeme mít také opačné setřídění – od největší hodnoty po nejmenší, kdy platí
n
i
i
i
a
a
a
≥
≥
≥
...
2
1
Například setříděním následujících přirozených čísel
7 2 3 1 6 7 3 4 5
dostaneme posloupnost
1 2 3 3 4 5 6 7 7
Pro popis algoritmů není podstatné, zda třídění je vzestupné nebo sestupné. Ve výkladu všech
algoritmů v tomto materiálu předpokládáme, že třídíme vzestupně.
Algoritmy třídění lze rozdělit do dvou základních skupin
• Algoritmy vnitřního třídění
• Algoritmy vnějšího třídění
Algoritmy vnitřního třídění mají tu základní vlastnost, že během třídění jsou všechny tříděné
prvky uloženy ve vnitřní paměti počítače. To je výhodné, protože veškeré operace třídění
(srovnání, přesuny) probíhají výlučně operacemi nad hodnotami ve vnitřní paměti.
V algoritmech vnějšího třídění jsou tříděné prvky uloženy v souborech na vnější paměti
(pevném disku). Tyto jsou průběžně v malých počtech přesouvány do vnitřní paměti, zde jsou
nad nimi provedeny příslušné operace (srovnání, přesuny) a následně jsou opět ukládány do
souborů na vnější paměť. Vnější třídění je obecně pomalejší než vnitřní třídění, protože operace
čtení a zápisu na vnější paměť jsou výrazně pomalejší než operace prováděné jen ve vnitřní
paměti. Vnější třídění proto používáme výlučně v těch případech, kdy tříděných údajů je tolik,
že se najednou nevejdou do paměti a nelze pro ně použít vnitřní třídění.