BPC-ALD - Skripta_rev2019_2

Popis algoritmu  

1.  Počáteční krok 

Na začátku celé pole, tj. všech n prvků tvoří nesetříděnou část. 

2.  Průběžný krok 

Nechť  setříděná  část,  která  je  na  začátku,  má  n-k  prvků  a  setříděná  část  za  ní  má  k prvků. 
V nesetříděné  části  vybereme  nejmenší  její  prvek.  Postupujeme  tak,  že  si  na  začátku 
zapamatujeme  pozici  prvního  prvku  nesetříděné  části.  Nyní  postupně  procházíme  prvky 
nesetříděné  části  počínaje  od  jejího  druhého  prvku  a  každý  z nich  srovnáváme  s prvkem  na 
zapamatované  pozici.  Jestliže  srovnávaný  prvek  je  menší,  jeho  pozice  se  stane  novou 
zapamatovanou pozicí. Je zřejmé, že na konci je na zapamatované pozici nejmenší prvek. Ten 
musíme  dostat  na  konec  setříděné  části.  To  nejjednodušeji  uděláme  tak,  že  ho  vyměníme 
s prvním prvkem v nesetříděné části. 

Po každém provedení průběžného kroku zvětšíme velikost setříděné části o jeden prvek. Tedy 
posuneme  rozhraní  mezi  setříděnou a nesetříděnou  částí  o  jednu  pozici  doprava.  V okamžiku, 

Třídění probíhá 
vybráním vždy 
nejmenšího prvku 
ze zbývajících 
prvků. 

− 29 − 

kdy  setříděná  část  bude  obsahovat  n-1  prvků,  je  třídění  ukončeno,  protože  v nesetříděné  části 
tímto zůstane už jen největší prvek, který je na konci a tudíž na své cílové pozici. 

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

              7  1  2  8  4  5  3  9