Bublinkové řazení

Znovu a znovu prochází seznam a prohazuje sousedy, kteří jsou ve špatném pořadí. Po každém průchodu je největší zbývající hodnota na konci.

nejlepší Ω(n)
průměrný Θ(n²)
nejhorší O(n²)
paměť O(1)
stabilní
bez paměti navíc

Co to znamená?

Nejlepší případ: jak roste čas s velikostí seznamu n, když je vstup pro tento algoritmus nejsnazší.
Průměrný: obvyklý růst času s n. Při n² trvá dvakrát víc hodnot asi čtyřikrát déle; n log n roste mnohem pomaleji.
Nejhorší: růst času na nejtěžším vstupu. Důležitý, když se řazení nesmí nikdy zpomalit.
Paměť: kolik paměti navíc je potřeba kromě seznamu. 1 znamená pár proměnných, n kopii seznamu.
Stabilní: dvě stejné hodnoty si zachovají původní pořadí. Důležité při řazení záznamů podle jednoho pole.
Bez paměti navíc: řadí přímo uvnitř seznamu, bez druhého seznamu.

porovnávání
přesun
na konečném místě

0 / 453 kroků

Porovnání Výměny

Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady

Rychlost 8 kroků/s

Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.

Zkuste: Zvolte téměř seřazený seznam. Po průchodu bez jediné výměny algoritmus skončí dřív.

Jak to funguje

Porovnává vždy dvě sousední hodnoty a prohodí je, když je levá větší. Největší hodnota tak v každém průchodu doputuje až na pravý konec, jako bublina stoupající vzhůru. Když průchod neudělá žádnou výměnu, seznam je už seřazený.

Kdy se hodí

Ve skutečných programech skoro nikdy, protože na dlouhých seznamech je pomalé. Pro výuku je ale skvělé: ukazuje základní myšlenku řazení porovnáváním a prohazováním. Rychlé je jen na seznamu, který už je seřazený.