BPC-ALD - Skripta_rev2019_2

2.  Průběžný krok 

Nechť  setříděná  část  je  nyní  tvořena  k prvky  a  za  ní  je  zbývajících  n-k  prvků,  které  tvoří 
nesetříděnou  část.  Vezmeme  první  prvek  z  nesetříděné  části  (ak+1),  uložíme  ho  do  pomocné 

proměnné, označme ji x, a pozici tohoto prvku považujeme za volnou. 

Nyní odzadu procházíme prvky v setříděné části a postupně pro indexy 

r = k, k-1, k-2, …  

srovnáváme, zda mezi prvkem ar a uloženým prvkem x platí 

x

a

r >

 . 

Pokud  ano,  posuneme  prvek  ar  o  jednu  pozici  dozadu  (tato  pozice  za  prvkem  je  v tomto  

okamžiku volná) a jeho původní pozice se nyní stane novou volnou pozicí. 

Celý proces srovnání skončí v okamžiku, kdy buďto pro některý prvek platí 

x

a

r ≤

anebo celá 

setříděna  část  je  už  porovnána  (a  rovněž  i  posunuta  dozadu).  Pozice  vložení  ve  chvíli,  kdy 
ukončíme  srovnávání,  odpovídá  stávající  volné  pozici.  Na  ni  uložíme  prvek  obsažený 
v proměnné x. 

Po  každém  provedení  průběžného  kroku  se  zvětší  velikost  setříděné  části  o  jeden  prvek,  až 
nakonec setříděná část bude zahrnovat všechny prvky. 

Procházíme 
setříděnou část 
od konce, až 
najdeme místo 
vložení. 

− 24 − 

Příklad. Mějme setřídit přirozená čísla 

              7  1  2  8  4  5  3  9  

Po prvním kroku bude pole rozděleno na dvě části: 

              7  |  1  2  8  4  5  3  9  

První prvek v nesetříděné části je číslo 1. Uložíme ho do proměnné x a jeho místo uvolníme