09-Trideni

(od konce k počátku ), dostal by se prvek 1 na svoje místo hned při 

prvním průchodu.

• Metodu modifikujeme tak, že směry procházení nesetříděné části se 

po každém průchodu střídají.

• V prvním průchodu je směr procházení od počátku ke konci.
• Ve druhém průchodu se prvních 𝑛 − 1 prvků prochází od konce k počátku.
• Ve třetím průchodu se prostředních 𝑛 − 2 prvků prochází opět od počátku ke 

konci.

• ....

Složitost modifikovaných algoritmů třídění 
přímou výměnou
• Ačkoli uvedené modifikace v některých případech snižují čas třídění, 

celková složitost metody zůstává stejná, tj. kvadratická.

Třídění přímým výběrem (Select Sort)

Třídění přímým výběrem (Select Sort)

• V průběhu třídění je pole s prvky rozděleno opět na dvě části - levá 

část obsahuje již správně setříděné prvky, pravá část obsahuje 
nesetříděné prvky.

• Nalezne se nejmenší prvek v nesetříděné části a ten se vymění s 

prvním prvkem nesetříděné části. Tím se setříděná část zvětší o jeden 
prvek.

Třídění přímým výběrem

• Na začátku tvoří nesetříděnou část všech 𝑛 prvků. 
• Průběžný krok:

1. Zapamatuj si index prvního prvku nesetříděné části a považuj ho dočasně za 

index nejmenšího prvku nesetříděné části.

2. Od druhé prvku nesetříděné části až po poslední prvek:

o Porovnej hodnotu prvku se zapamatovaným indexem s aktuálním prvkem. Pokud je 

aktuální prvek menší, zapamatuj si jeho index a považuj ho dočasně za index nejmenšího 
prvku.

3. Vyměň prvek na zapamatované pozici s prvním prvkem nesetříděné části.
4. Zvětši setříděnou část o 1 prvek.
5. Pokud setříděná část obsahuje 𝑛 − 1 prvků, konči. Jinak se vrať na bod 1. 

Příklad činnosti algoritmu třídění přímým 
výběrem
• 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