08-Trideni_uvod

BPC-ALD

8. přednáška

Úvod do třídicích algoritmu, definice třídicí úlohy, vnitřní a vnější 

metody třídění, třídění přímým vkládáním (Insert Sort) a odvození 

složitosti algoritmu

rev. 2019.3

Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz)

Třídění

• Algoritmy pro třídění patří do skupiny základních, velmi používaných 

algoritmů.

• Mějme vstupní množinu dat obsahující n prvků:

a1, a2, ..., an.

• Pro prvky množiny musí definováno srovnání dle velikosti (<, =, >). 
• Cílem je seřadit prvky do posloupnosti:

ai

1

, ai

2

, ..., ai

n.

Třídění

• Při třídění vzestupně (od nejmenšího prvku po největší) musí platit:

ai

1

≤ a

i2

≤ ... ≤ a

in

• Např.: 3, 5, 5, 10, 11, 20, 20, 33

• Při třídění sestupně (od největšího prvku po nejmenší) musí platit:

ai

1

≥ ai

2

≥ ... ≥ ai

n

• Např.: 33, 20, 20, 11, 10, 5, 5, 3

Třídění

• Pro popis algoritmů není podstatné, zda použijeme vzestupné nebo 

sestupné třídění.

• V dalším výkladu budeme používat vzestupné třídění.

Vnitřní x vnější algoritmy třídění

• Algoritmy vnitřního třídění

• Během třídění jsou všechny tříděné prvky uloženy v operační paměti počítače.
• Veškeré operace (srovnání, přesuny) probíhají výlučně s hodnotami uloženými 

ve vnitřní paměti. 

• Algoritmy vnějšího třídění

• Během třídění jsou tříděné prvky uloženy v souborech ve vnější paměti (disk).
• Tříděné prvky jsou po skupinách o relativně malém počtu přesouvány z disku 

do vnitřní paměti, jsou na nich provedeny operace třídění a pak jsou 
přesunuty zpět do souboru (resp. souborů) na disk.

Vnitřní x vnější algoritmy třídění

• Algoritmy vnějšího třídění jsou obecně pomalejší než algoritmy 

vnitřního třídění, protože práce s vnější pamětí (diskem) je řádově 
pomalejší než práce s vnitřní pamětí.

• Algoritmy vnějšího třídění používáme pouze v případech, kdy je