Obsah:
Definice - Co znamená Bubble Sort?
Bubble sort je algoritmus třídění, který funguje opakovaným procházením seznamů, které je třeba třídit, porovnáním každé dvojice sousedních položek a zaměněním, pokud jsou v nesprávném pořadí. Tento postup předávání se opakuje, dokud nejsou vyžadovány žádné swapy, což znamená, že seznam je seřazen. Řazení bublin získává svůj název, protože menší prvky bublinkují směrem k horní části seznamu.
Bublinové řazení se také označuje jako klesající nebo srovnávací řazení.
Techopedia vysvětluje bublinové řazení
Řazení bublin má nejhorší případ a průměrnou složitost O (n2), kde n je počet seřazených položek. Na rozdíl od jiných algoritmů třídění, bublinové řazení detekuje, zda je tříděný seznam efektivně zabudován do algoritmu. Výkon řazení bublin v již seřazeném seznamu je O (n).
Pozice prvků v bublinovém řazení hraje důležitou roli při určování výkonu. Velké prvky na začátku nepředstavují problém, protože se snadno zaměňují. Malé prvky směrem ke konci se pomalu pohybují na začátek. Proto se tyto prvky nazývají králíci a želvy.
Algoritmus třídění bublin lze optimalizovat umístěním větších prvků do konečné polohy. Po každém průchodu jsou všechny prvky po posledním swapu tříděny a není třeba je znovu kontrolovat, čímž se přeskočí sledování swapovaných proměnných.
