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.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- ano
- ano
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ě
Dvojice ve špatném pořadí: 154 (na začátku: 154) ve špatném pořadí srovnáno Obě osy: hodnoty od nejmenší po největší
Stiskněte Přehrát: čáry ukazují, jak během řazení rostou náklady
Stiskněte Přehrát nebo procházejte algoritmus krok po kroku.
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ý.