10-Trideni_ucinejsi_metody

• Aby bylo co třídit, musí být v každé posloupnosti minimálně dva 

prvky, proto pro nejvyšší hodnotu ℎ platí: ℎ𝑚𝑎𝑥 ≤

𝑛

2. 

Shellovo třídění 

• U prvního průchodu je hodnota ℎ velká, podposloupnosti jsou tedy 

krátké a nalezení pozic vložení probíhá rychle. 

• U dalších průchodů se délka podposloupností sice prodlužuje, ale 

protože prvky byly již přiblíženy ke své cílové pozici, budou většinou 
pozice vložení poměrně blízko ke konci setříděné části, což znamená 
nižší počet srovnání a přesunů. 

• Při posledním kroku je ℎ = 1, proběhne tedy klasické třídění přímým 

vkládáním, které zaručí že výsledkem bude vždy plně setříděná 
posloupnost. 

Příklad činnosti algoritmu Shellova třídění 

• Je dána posloupnost čísel: 7 1 2 8 2 4 5 3 1 9 . 
• Popište konkrétně jednotlivé kroky třídění a uveďte po každém kroku  

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

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

Složitost algoritmu Shellova třídění 

• Složitost Shellova třídění je:  Θ 𝑛1.5 . 
• Vlastní odvození je poměrně složité, proto jej nebudeme provádět. 

Rychlé třídění výběrem (Quick Sort) 

Princip metody Quick Sort 

• Využívá strategii: Rozděl a panuj. Autor: Tony Hoare, 1961. 
• V poli zvolíme prvek, označme ho 𝑎𝑠. 
• Postupnými výměnami prvků vytvoříme v poli dvě části: 

• Část A obsahuje prvky menší nebo rovny prvku 𝑎𝑠. 
• Část B obsahuje prvky větší nebo rovny prvku 𝑎𝑠. 

A 

B 

𝑎𝑠 

𝑎𝑖 ≤ 𝑎𝑠 

𝑎𝑖 ≥ 𝑎𝑠 

Princip metody Quick Sort 

• Dále stejným způsobem třídíme samostatně části A a B. 
• Postup, který jsme nejprve aplikovali na celé pole, rekurzivně 

aplikujeme samostatně na obě menší části A a B. 

• Tříděné části se stávají postupně menší a menší, až bude tříděná část