BPC-ALD - Skripta_rev2019_2

Stav po prvním průchodu je   

              1  3  2  8  4  5  7  |  9  

Stav po druhém průchodu je   

              1  2  3  4  5  7  |  8  9  

Zbývá ještě 5 průchodů s délkami procházených částí 6,5,4,3 a 2. Přitom viditelně všechny jsou 
zbytečné,  neboť  posloupnost  je  v této  chvíli  už  setříděna.  Proto  algoritmus  rozšíříme  tak,  že 
v každém průchodu sledujeme, zda v něm došlo vůbec k nějaké výměně. Jestliže ne, třídění se 
ukončí. V našem příkladu by takto rozšířený algoritmus provedl ještě 3. průchod, ve kterém by 
se  zjistilo,  že  žádná  výměna  už  během  něho  neproběhla,  a  tím  by  se  třídění  ukončilo.  Tedy 
zbývající 4 průchody by už vůbec neproběhly. 

Vezměme další příklad, z něhož vyplyne, jak ještě dále lze zlepšit vlastnosti metody: 

              2  3  4  5  7  8  9  1  

Stav po prvním průchodu 

              2  3  4  5  7  8  1  |  9  

Stav po druhém průchodu 

              2  3  4  5  7  1  |  8  9  

I když výchozí posloupnost vypadá pro třídění velmi příznivě, neboť je zapotřebí jen přesunout 
prvek  s hodnotu  1  na  začátek,  přesto  to  probíhá  velmi  pomalu.  Je  to  dáno  skutečností,  že  při 
procházení směrem od začátku ke konci se prvky s velkými hodnotami rychle dostávají dozadu, 

Naprogramování 
je velmi snadné. 

Pokud nedojde 
k žádné 
výměně, 
můžeme třídění 
ukončit.