BPC-ALD - Skripta_rev2019_2

Někdy je výhodné  
posloupnost 
procházet 
střídavě od 
začátku a od 
konce.

Metoda je známá 
pod názvem 
bublinkové 
třídění. 

− 28 − 

naproti  prvky  s malými  hodnotami  postoupí  dopředu  v každém  průchodu  jen  o  jednu  pozici. 
Kdybychom v uvedené posloupnosti použili opačný směr, tedy odzadu směrem dopředu, dostal 
by  se  prvek  s hodnotou  1  na  své  místo  hned  v  prvním  průchodu.  Z toho  vychází  modifikace 
metody, ve které se směry procházení v každém průchodu střídají. V prvním průchodu je směr 
procházení  odpředu,  čímž  se  poslední  prvek  dostane  na  své  místo.  V druhém  průchodu  se 
prvních  n-1  prvků  prochází  směrem  odzadu,  čímž  se  první  prvek  dostane  na  své  místo.  Ve 
třetím  průchodu  se  n-2  středních  prvků  prochází  opět  směrem  odpředu,  čímž  se  předposlední 
prvek dostane na své místo. Atd. 

V našem příkladu bude stav po prvním průchodu 

              2  3  4  5  7  8  1  |  9  

Stav po druhém průchodu 

              1  |  2  3  4  5  7  8  |  9  

Ve třetím průchodu se bude procházet střední posloupnost, přičemž se zjistí, že nedojde k žádné 
výměně, čímž se po tomto průchodu třídění ukončí. 

Poznamenejme na závěr, že ačkoliv tyto modifikace v určitých případech snižují čas třídění,  na 
celkovou časovou složitost metody nemají vliv. Ta zůstává stále kvadratická. 

3.2.3  Třídění přímým výběrem 

Při  třídění  přímým  výběrem  je  rovněž  v průběhu  třídění  pole  s prvky  rozděleno  na  dvě  části. 
Zde ale část obsahující již setříděné prvky je první a část s doposud nesetříděnými prvky je za 
ní.