BPC-ALD - Skripta_rev2019_2

              7  |  

•  2  8  4  5  3  9  

Srovnáme 7 s x 

→ posunutí 7 doprava: 

•  |  7  2  8  4  5  3  9  

Už není co srovnávat, vložíme x na volnou pozici a posuneme hranici setříděné části: 

              1  7  |  2  8  4  5  3  9  

Další krok - uložíme první prvek 2 do proměnné x a jeho místo uvolníme: 

              1  7  |  

•  8  4  5  3  9  

Srovnáme 7 s x 

→ posunutí 7 doprava: 

              1  

•  |  7  8  4  5  3  9  

Srovnáme 1 s x 

→ vložení x a posunutí hranice setříděné části: 

              1  2  7  |  8  4  5  3  9  

Další krok - uložíme první prvek 8 do proměnné x a jeho místo uvolníme: 

              1  2  7  |  

•  4  5  3  9  

Srovnáme 7 s x 

→ vložení x a posunutí hranice setříděné části: 

              1  2  7  8  |  4  5  3  9  

Atd. 

Složitost metody Uvedený  algoritmus  třídění  je  založen  na  operacích  srovnání  a  vložení.  Vezměme  nejprve 
operaci  srovnání.  Nechť  počet  prvků  v setříděné  části  je  k.  Abychom  zjistili  místo  vložení, 
uděláme 1 až k srovnání. Jedno srovnání v případě, kdy se prvek vkládá hned na konec setříděné 
části, k srovnání v případě, kdy prvek patří na první nebo druhou pozici v setříděné části. Odtud 
pro jeden krok dostáváme