BPC-ALD - Skripta_rev2019_2

Klíčová slova: Srovnání, vložení, výběr, výměna, bublinkové třídění. 

Potřebný čas: 3 hodiny 

3.2.1  Třídění přímým vkládáním 

Předpokládáme, že tříděné prvky máme na začátku uspořádány v nějakou posloupnost. V praxi 
při  implementaci  metod  třídění  používáme  pro  uložení  prvků  pole.  Výchozí  posloupnost  nám 
tedy tvoří počáteční uložení prvků v poli. 

Počet tříděných prvků nechť je n. Prvky si označme 

n

a

a

a

...

,

,

2

1

Pole, ve kterém jsou uloženy prvky, je v průběhu třídění rozděleno na dvě části - setříděnou část 
(ta  je  první)  a  nesetříděnou  část.  V každém  kroku  vezmeme  první  prvek  v nesetříděné  části, 
projdeme setříděnou část, najdeme v ní místo vložení a na toto místo prvek vložíme. Vložení se 
provede tak, že posuneme všechny prvky počínaje místem vložení až po konec setříděné části o 
jednu  pozici  dozadu,  aby  se  uvolnilo  místo  pro  vkládaný  prvek,  a  na  uvolněnou  pozici  nový 
prvek vložíme. Hledání pozice vložení lze udělat postupným procházením od začátku setříděné 

Prvky při třídění 
vkládáme nebo 
vyměňujeme 
nebo vybíráme. 

Třídění probíhá 
vkládáním prvků 
na jejich cílové 
místo. 

− 23 − 

části a srovnáváním vkládaného prvku s prvky setříděné části. Výhodnější ale v tomto případě je 
zvolit opačný směr, začít procházení od konce setříděné části, neboť můžeme přitom souběžně 
dělat  i  posouvání  prvků  setříděné  části  o  jednu  pozici  dozadu.  Z této  možnosti  vychází 
následující algoritmus. 

Popis algoritmu 

1.  Počáteční krok 

Na  začátku  vytvoříme  počáteční  rozdělení  pole  na  setříděnou  a  nesetříděnou  část.  Setříděnou 
částí bude první prvek v poli, nesetříděnou částí bude zbývajících n-1 prvků.