10-Trideni_ucinejsi_metody

Popis metody Quick Sort 

•

𝑖 = 𝑖 + 1 
Pokud 𝑗 > 𝑘, 𝑗 = 𝑗 − 1, jinak třídící krok je možné ukončit. 

• Pokud 𝑖  > 𝑗 třídící krok ukončíme. 

• Po dokončení třídícího kroku je: 

• buď 𝑖 = 𝑗 + 1 
• nebo 𝑖 = 𝑗 + 2 

Popis metody Quick Sort 

• Po dokončení třídícího kroku je 𝑖 = 𝑗 + 1, pole je rozděleno na dvě 

části: 
 

A 

B 

≤ 𝑡𝑚𝑝 

≥ 𝑡𝑚𝑝 

𝑘 

𝑗 𝑖 

𝑙 

• Příklad: počáteční pole má hodnoty 3 4 1. 
• Po provedení prvního třídícího kroku dostaneme dvě pole 3 1|4. 

Popis metody Quick Sort 

• Po dokončení třídícího kroku je 𝑖 = 𝑗 + 2, pole je rozděleno na dvě 

části a mezi nimi je jeden prvek s hodnotou uloženou v 𝑡𝑚𝑝: 
 

A 

B 

≤ 𝑡𝑚𝑝 

≥ 𝑡𝑚𝑝 

𝑘 

𝑗 

𝑖 

𝑙 

• Příklad: počáteční pole má hodnoty 5 3 4 1. 
• Po provedení prvního třídícího kroku dostaneme dvě pole 1|3|4 5. 

tmp 

Popis metody Quick Sort 

• Má-li část A více jak jeden prvek, pak rekurzivně provedeme třídící 

krok na té části pole, jejíž počáteční a koncový index je dán 
současnými hodnotami 𝑘, 𝑗. 

• Má-li část B více jak jeden prvek, pak rekurzivně provedeme třídící 

krok na té části pole, jejíž počáteční a koncový index je dán 
současnými hodnotami 𝑖, 𝑙. 

Příklad činnosti algoritmu Quick Sort  

• Je dána posloupnost čísel: 7 1 9 5 4 8 3 2 . 
• 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 Quick Sort 

• Složitost metody je v nejhorším případě kvadratická. 
• Typicky na reálných datech, ale dosahuje: 𝑛 𝑙𝑜𝑔2 𝑛 .