10-Trideni_ucinejsi_metody

obsahovat pouze jeden prvek a rekurzivní zpracování končí. 

Princip metody Quick Sort 

• Jak zvolit prvek 𝑎𝑠 (tzv. pivot)? 
• Optimální by byla taková volba, že obě části (A a B) budou obsahovat 

stejný počet prvků. 

• Vyžadovalo by to najít prvek, jehož hodnota leží uprostřed hodnot prvků pole. 
• To by však bylo časově tak náročné, že by se použití metody nevyplatilo. 

• Prakticky se volí prvek 𝑎𝑠 např.: 

• Prostřední prvek pole. 
• Náhodně zvolený prvek pole (použití generátoru náhodných čísel). 
• Medián ze tří prvků - prvního, posledního a prostředního. 

• Dále budeme jako pivot používat prostřední prvek. 

Popis metody Quick Sort 

• Zavedeme následující značení: 

•

𝑎 - jméno pole s tříděnými prvky 

•

𝑘, 𝑙 - index počátku resp. konce části pole, která je právě tříděna 

•

𝑠 - index prostředního prvku (pivota) 

•

𝑖, 𝑗 - průběžné indexy používané pro procházení pole zepředu a odzadu 

𝑎 

𝑘  

𝑗 

𝑖 

𝑙 

𝑠 

Popis metody Quick Sort 

• Počáteční krok 

• Na začátku je tříděnou oblastí celé pole 𝑎. 
• Nastavíme: 𝑘 = 0 

 𝑙 = 𝑛 − 1. 

Popis metody Quick Sort 

• Třídící krok 

• Najdeme index prvku uprostřed tříděné části: 𝑠 =

𝑘+𝑙

2  . 

Prvek s indexem 𝑠 uložíme do proměnné 𝑡𝑚𝑝. 

• Průběžné indexy nastavíme na začátek a konec právě tříděné oblasti: 

𝑖 = 𝑘 

𝑗 = 𝑙. 

• Tříděnou část procházíme směrem dozadu. Zvětšujeme index 𝑖 až narazíme na 

prvek 𝑎𝑖 ≥ 𝑡𝑚𝑝.  

• Následně procházíme tříděnou část směrem dopředu. Zmenšujeme index 𝑗 až 

narazíme na prvek 𝑎𝑗 ≤ 𝑡𝑚𝑝. 

• Pokud nastane, že 𝑖 > 𝑗 třídící krok ukončíme. 
• Prvky 𝑎𝑖 a 𝑎𝑗 mezi sebou vyměníme.