09-Trideni

2

=

𝑛2 − 𝑛

2

Složitost algoritmu třídění přímou výměnou

• Nyní stanovíme celkový počet operací výměny dvou prvků.
• Maximálně se můžeme provést tolik operací výměny, kolik bylo 

provedeno operací srovnání: 

𝑛2−𝑛

2

• Minimální počet výměn je 0 (algoritmus jsme aplikovali na již 

setříděnou posloupnost prvků)

• Průměrný počet výměn: 

0+

𝑛2−𝑛

2

2

=

𝑛2−𝑛

4

Složitost algoritmu třídění přímou výměnou

ai-1

ai

tmp

1.

2.

3.

• Operace výměna dvou prvků není základní operací - lze ji rozdělit na 3 

dílčí operace přesunů:

1. Přesun hodnoty prvku ai-1 do pomocné proměnné tmp.
2. Přesun hodnoty prvku ai na místo prvku ai-1.
3. Přesun hodnoty pomocné proměnné tmp na místo prvku ai.

Složitost algoritmu třídění přímou výměnou

• Průměrný počet přesunů: 

3 𝑛2−𝑛

4

.

• Maximální počet přesunů: 

3 𝑛2−𝑛

2

.

• Obě operace (srovnání, přesun) mají stejnou - kvadratickou míru 

složitosti.

• Výsledná míra složitosti je tedy kvadratická.

Modifikace algoritmu třídění přímou 
výměnou
• Pokud během průchodu nesetříděné části nedojde k žádné výměně, 

není nutno provádět další průchody – sekvence je již setříděna .

• Příklad posloupnosti: 3 1 9 2 8 4 5 7 . 

Modifikace algoritmu třídění přímou 
výměnou (Shaker Sort)
• Příklad posloupnosti: 2 3 4 5 7 8 9 1 .
• I když výchozí posloupnost je téměř setříděná, třídění bude probíhat 

velmi pomalu - prvek 1 se dostane na svoje místo až při posledním 
průchodu.

• Procházíme-li posloupnost směrem od počátku ke konci : 

• Prvky s velkými hodnotami se dostávají rychle na konec .
• Naproti tomu prvky s malými hodnotami postupují dopředu v každém 

průchodu pouze o 1 pozici.

Modifikace algoritmu třídění přímou 
výměnou (Shaker Sort)
• Příklad posloupnosti: 2 3 4 5 7 8 9 1 .
• Kdybychom procházeli výše uvedenou posloupnost v opačném směru