BPC-ALD - Skripta_rev2019_2

            1  |  2  3  4  

Část A už má jeden prvek, vezmeme část B:  

             2  3  4  

Na začátku i = 1, j = 3, střední prvek je x = 3. 

Po hledání i = 2, j = 2 

            2  3  4  

a výměna (sama se sebou)  

            2  3  4  

Nové indexy i = 3, j = 1 - třídící krok končí. Rozdělení pole je 

3

− 38 − 

            2  |  3  |  4  

čímž je tato část dokončena. 

Zbývá ještě část B z prvního třídícího kroku: 

           5 8  9  7  

Na začátku i = 4, j = 7, střední prvek je x = 8. Atd. 

Složitost metody Stanovení složitosti metody je poněkud problematičtější. Ta závisí na tom, v jakém poměru se 
tříděná  část  rozdělí  na  nové  části  A  a  B.  Nejhorší  případ  nastane,  když  jedna  z těchto  částí 
obsahuje  jen  jeden  prvek  a  ta  druhá  zbývající  prvky.  Pak  by  následující  třídící  krok  proběhl 
vždy jen pro tu větší část a ta by měla vždy o jeden prvek méně, než tomu bylo v předchozím 
kroku.  Tedy  třídící  kroky  by  proběhly  postupně  pro  části  s počty  prvků  n,  n-1,  …,  2.  Počet 
srovnání v každém třídícím kroku bude záviset jednak na počtu prvků v procházené části a také 
určitým  způsobem  na  tom,  kolik  proběhne  výměn  (neboť  po  každé  výměně  se  změní  oba 
indexy).  Počet  srovnání  je  maximálně o 1  větší, než je počet prvků v procházené  části. Tento 
největší počet srovnání nastane v případě, kdy procházená část už je setříděná. Nechť například 
procházená část je