09-Trideni

BPC-ALD

9. přednáška

Třídění přímou výměnou (Bubble Sort), modifikace algoritmu Bubble

Sort, odvození složitosti algoritmu, třídění přímým výběrem (Select

Sort), odvození složitosti algoritmu

rev. 2019.2

Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz)

Třídění přímou výměnou (Bubble Sort, 
bublinkové třídění)
• Procházíme pole prvků směrem od začátku ke konci.
• Porovnáváme vždy dva sousední prvky. Pokud nejsou ve správném 

pořadí, vzájemně je vyměníme.

• Po průchodu celým polem se největší prvek vždy dostane na poslední místo v 

poli, tedy na svou cílovou pozici.

• V dalším kroku celý postup opakujeme, ale už pouze s prvními n-1

prvky. 

• Druhý největší prvek se dostane na svou cílovou pozici.

Třídění přímou výměnou (bublinkové třídění)

• Snížíme počet prvků, které budeme procházet o jeden a postup 

porovnání a výměny prvků opakujeme pro n-2 prvků.

• Opakujeme až do okamžiku, kdy je počet prvků roven dvěma. 
• V posledním kroku bude procházet pouze část se dvěma prvky.

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

částečně setříděnou posloupnost.

• (Uvažujme vzestupné třídění.)

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

• Algoritmus je založen na operacích srovnání a výměny dvou prvků.
• Nejprve se zabývejme počtem operací srovnání.
• V prvním průchodu pracujeme s 𝑛 prvky, musíme provést 𝑛 − 1

srovnání dvou čísel.

• Ve druhém průchodu pracujeme s 𝑛 − 1 prvky, musíme provést 𝑛 − 2

srovnání dvou čísel. 

• V posledním průchodu pracujeme pouze se dvěma prvky a provádíme 

pouze jedno srovnání dvou čísel.

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

• Celkový počet srovnání:

𝑛 − 1 + 𝑛 − 2 + ⋯ + 1 =

𝑛 − 1 1 + 𝑛 − 1