08-Trideni_uvod

množství tříděných údajů tak velké, že se nevejde do vnitřní paměti.

Metody vnitřního třídění

• Algoritmy vnitřního třídění jsou založeny na dvou základních 

operacích - srovnání a přesun.

• Podle toho,  jak přesuny probíhají, dělíme algoritmy do tří základních 

skupin:

• Třídění vkládáním
• Třídění výměnou
• Třídění výběrem

Třídění přímým vkládáním (Insert Sort)

• Předpokládejme posloupnost a

1, a2, ..., an obsahující n nesetříděných 

prvků uložených např. v jednorozměrném poli.

• V průběhu třídění je pole rozděleno na 2 části:

• První část obsahuje setříděné prvky.
• Druhá část obsahuje nesetříděné prvky.

• V každém kroku vezmeme prvek z nesetříděné části, najdeme pro něj 

odpovídající místo v setříděné části a na toto místo prvek vložíme.

Popis algoritmu třídění přímým vkládáním

• Počáteční krok:

Setříděná část je tvořena prvním prvkem a1, zbývajících n-1 prvků 

tvoří nesetříděnou část.

• Průběžný krok:

Setříděná část je tvořena prvními k prvky, nesetříděná zbývajícími n-k
prvky. 

1. Vezmi první prvek nesetříděné části (ak+1) a vlož ho do pomocné proměnné 

tmp. Pozici prvku ak+1 považuj za volnou.

Popis algoritmu třídění přímým vkládáním

2. Odzadu procházej prvky v setříděné části.

Pokud bude ar > tmp (r = k, k-1, k-2, ... , 1), posuň prvek ai o jednu pozici 

dozadu. Původní pozice prvku ar se stává novou volnou pozicí. 

Pokud je ar > tmp pokračuj bodem 3. 

3. Vlož hodnotu tmp na volnou pozici.

(Pozice vložení ve chvíli, kdy ukončíme srovnávání odpovídá stávající volné 
pozici.)

4. Zvětši velikost setříděné části o jeden prvek.

Pokud setříděná část neobsahuje všechny prvky opakuj bod 2. Jinak 
algoritmus ukonči.

Příklad činnosti algoritmu třídění přímým 
vkládáním
• Je dána posloupnost čísel: 7 1 2 8 2 4 5 3 1 9 .
• Popište konkrétně jednotlivé kroky třídění a uveďte po každém kroku