BPC-ALD - Skripta_rev2019_2

v každé byly aspoň dva prvky. Podíváme-li se na optimální posloupnost kroků, vidíme, 
že její členy jsou mocniny čísla 2 zmenšené o 1. Tedy hledáme největší číslo k, proto 
které platí: 

1

2

500

−

≥ k

Zřejmě tomu vyhovuje k=8 a optimální posloupnost kroků je 

255, 127, 63, 31, 15, 7, 3, 1 

3.3.2  Rychlé třídění výměnou (Quicksort) 

Studijní cíle:  Tato  část  vysvětluje  princip  rychlého  třídění  výměnou  a  poskytuje  podrobný 
popis algoritmu tak, aby ho studující byl schopen případně implementovat. 

Klíčová slova: Quicksort. 

Potřebný čas: 1 hodina 30 minut. 

Budeme  vycházet  opět  z předpokladu,  že  třídění  probíhá  v poli,  přičemž  každý  prvek  pole 
reprezentuje jeden tříděný prvek. Počet tříděných prvků je n a indexování pole je od 0, což je 
v dnešních programovacích jazycích obvyklé. 

Princip  metody  spočívá  v tom,  že  v poli  zvolíme  určitý  prvek,  označme  ho  as,  a  postupnými 

výměnami  z  tříděného  pole  vytvoříme  dvě  části.  V první  části  (označme  ji  A)  budou  prvky, 
které nejsou větší než zvolený prvek as, a v druhé části (B) budou prvky, které nejsou menší než 

as. 

Principem metody 
je provedení 
výměn tak, že pole 
se jimi rozdělí na 
dvě části, mezi 
nimiž už žádné 
výměny nebudou. 

− 35 − 

Je  zřejmé,  že  v dalším  pokračování  třídění,  tj.  při  provádění  dalších  výměn  už  stačí  jen 
vyměňovat samostatně prvky obsažené v části A a samostatně prvky obsažené v části B. Tudíž 
postup,  který  jsme  na  začátku aplikovali na celé pole, nyní rekurzivně  aplikujeme  samostatně 
jen  na část A a pak  na část  B. Postupným rekurzivním opakováním tohoto postupu se tříděné 
části stávají postupně stávají menší, až nakonec nastane stav, že obsahují jen jeden prvek, čímž 
to končí.