09-Trideni

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

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

Složitost algoritmu třídění přímým výběrem

• Algoritmus je založen na operacích výběru a výměny dvou prvků.
• Uvažujme nejprve operaci výběru.
• Je-li nesetříděná část tvořena 𝑘 prvky, potřebujeme k nalezení jejího 

nejmenšího prvku 𝑘 − 1 srovnání.

• Délky nesetříděných částí jsou v jednotlivých krocích 𝑛, 𝑛 − 1 , … , 2
• Proto je celkový počet srovnání: 

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

𝑛 − 1 1 + 𝑛 − 1

2

=

𝑛2 − 𝑛

2

Složitost algoritmu třídění přímým výběrem

• Dále uvažujme operaci výměny vybraného nejmenšího prvku s prvním 

prvkem nesetříděné části.

• Operace výměna je provedena v každém kroku třídění.
• Počet kroků třídění je 𝑛 − 1.
• Operace výměna se skládá se skládá ze 3 kroků přesunů.
• Celkový počet přesunů je 3 𝑛 − 1 .

Složitost algoritmu třídění přímým výběrem

• Operace výběru má kvadratickou míru složitosti, zatímco operace 

výměny resp. přesunů má lineární míru složitosti. 

• Výsledná míra složitosti algoritmu je dána operací s největší mírou 

složitosti.

• Výsledná míra složitosti je tedy kvadratická.

Porovnání složitosti jednoduchých metod 
třídění

Insert Sort

Bubble Sort

Select Sort

Srovnání

Přesuny

Srovnání

Přesuny

Srovnání

Přesuny

Maximálně

𝑛 − 1 𝑛

2

𝑛2 − 𝑛

2

𝑛2 − 𝑛

2

3 𝑛2 − 𝑛

2

𝑛2 − 𝑛

2

3 𝑛 − 1

Průměrně

𝑛2 + 𝑛 − 2

4

𝑛2 − 𝑛

4

𝑛2 − 𝑛

2

3 𝑛2 − 𝑛

4

𝑛2 − 𝑛

2

3 𝑛 − 1

Porovnání složitosti jednoduchých metod 
třídění
• Všechny uvedené jednoduché metody třídění mají kvadratickou 

složitost.

• Přesné vztahy pro počty operací se pro jednotlivé metody liší.
• Konkrétní rychlost jednotlivých metod bude také závislá na charakteru 

vstupních dat (např. zda je vstupní posloupnost téměř setříděná).