08-Trideni_uvod

částečně setříděnou posloupnost.

• (Uvažujme vzestupné třídění.)

Složitost algoritmu třídění přímým vkládáním

• Algoritmus je založen na operacích srovnání a přesunů.
• Předpokládejme počet prvků v setříděné oblasti k.
• Nejprve se zabývejme počtem operací srovnání.
• Abychom zjistili místo vložení, musíme udělat 1 až k srovnání.

• Jedno srovnání, když prvek vkládáme hned na konec setříděné části.
• k srovnání, když prvek vkládáme na začátek setříděné části (tj. první nebo 

druhou pozici).

• Průměrný počet srovnání v průběžném kroku: 

1+𝑘

2

• Maximální počet srovnání v průběžném kroku: 𝑘

Složitost algoritmu třídění přímým vkládáním

• Délky setříděných částí v jednotlivých krocích jsou: 𝑘 = 1, 2, … , 𝑛 − 1.

• Průměrný počet srovnání: 

2+3+⋯+𝑛

2

=

1+2+3+⋯+ 𝑛−1 +𝑛 −1

2

.

• 1 + 2 + 3 + ⋯ + 𝑛 je aritmetická řada, pro jejíž součet platí vztah:   

𝑠𝑛 =

𝑛 𝑎1+𝑎𝑛

2

.

• Pro řadu: 1 + 2 + 3 + ⋯ + 𝑛 =

𝑛 1+𝑛

2

=

𝑛2+𝑛

2

.

• Potom pro: 

2+3+⋯+𝑛

2

=

1+2+3+⋯+ 𝑛−1 +𝑛 −1

2

=

𝑛2+𝑛

2

−1

2

=

𝑛2+𝑛−2

4

.

Složitost algoritmu třídění přímým vkládáním

• Průměrný počet srovnání tedy je: 

𝑛2+𝑛−2

4

• Maximální počet srovnání: 

1 + 2 + 3 + ⋯ + 𝑛 − 1 =

𝑛 − 1 1 + 𝑛 − 1

2

=

𝑛 − 1 𝑛

2

• Operace srovnání má kvadratickou složitost bez ohledu na to, zda 

bereme průměrnou nebo maximální hodnotu možných srovnání.

Složitost algoritmu třídění přímým vkládáním

• Nyní se budeme zabývat počtem operací přesunu prvku o jednu pozici 

dozadu.

• V jednom průběžném kroku proběhne 0 až k operací přesunu.

• 0, když první prvek nesetříděné části zůstává na své pozici (je již rovnou 

správně umístěn).

• k, když prvek vkládáme až na první místo v setříděné části.