Třídění bublin
Příklad třídění bublin. Počínaje od začátku seznamu porovnejte každý sousední pár, vyměňte jejich pozici, pokud nejsou ve správném pořadí (druhý je menší než první). Po každé iteraci je třeba porovnat o jeden prvek méně (poslední), dokud nezbývají žádné další prvky k porovnání.
PerformanceEdit
Třídění bublin má nejhorší případ a průměrnou složitost О (n2), kde n je počet tříděných položek. Nejpraktičtější třídicí algoritmy mají podstatně lepší nejhorší případy nebo průměrnou složitost, často O (n log n). Dokonce i jiné algoritmy třídění О (n2), jako je například vkládání, obvykle běží rychleji než třídění podle bublin a nejsou složitější. Třídění bublin proto není praktickým algoritmem třídění.
Jedinou významnou výhodou, kterou má třídění bublin oproti většině ostatních algoritmů, a to i při rychlém řazení, ale nikoli při vkládání, je schopnost zjistit, že je seznam seřazen. efektivně je zabudován do algoritmu. Pokud je seznam již seřazen (v nejlepším případě), je složitost bublinového řazení pouze O (n). Naproti tomu většina ostatních algoritmů, i těch s lepší průměrnou složitostí, provádí celý proces třídění na množině, a proto jsou složitější. Nejen, že vkládání řazení sdílí tuto výhodu, ale také funguje lépe na seznamu, který je v podstatě seřazen (s malým počtem inverzí). Pokud je toto chování navíc požadováno, lze ho triviálně přidat do jakéhokoli jiného algoritmu kontrolou seznamu před spuštěním algoritmu.
V případě velkých kolekcí by se mělo vyhnout třídění bublin. V případě obráceně seřazené sbírky to nebude efektivní.
Rabbits and TurtlesEdit
Vzdálenost a směr, kterým se prvky musí během třídění pohybovat, určují výkonnost bublinového třídění, protože prvky se pohybují různými směry různými rychlostmi. Prvek, který se musí pohybovat na konec seznamu, se může pohybovat rychle, protože se může účastnit postupných swapů. Například největší prvek v seznamu vyhraje každý swap, takže se přesune na jeho seřazená pozice při prvním průchodu, i když začíná blízko začátku. Na druhou stranu se prvek, který se musí pohybovat na začátek seznamu, nemůže pohybovat rychleji než jeden krok na průchod, takže se prvky pohybují na začátek velmi pomalu. nejmenší prvek je na konci seznamu, jeho přesunutí na začátek bude trvat n-1 průchodů. To vedlo k tomu, že tyto typy prvků byly pojmenovány králíci a želvy, podle znaků v Ezopově bajce Želva a zajíc.
Různé bylo vyvinuto úsilí k eliminaci želv s cílem zlepšit rychlost třídění bublin. Koktejlové třídění je obousměrné třídění bublin, které jde od začátku do konce, a pak se obrátí a jde od začátku do začátku. Dokáže docela dobře pohybovat želvami, ale zachovává si nejhorší složitost O (n2). Hřebenové třídění porovnává prvky oddělené velkými mezerami a může extrémně rychle přesunout želvy, než přejde na menší a menší mezery k vyhlazení seznamu. Jeho průměrná rychlost je srovnatelná s rychlejšími algoritmy, jako je quicksort.
Podrobný příkladEdit
Vezměte pole čísel „5 1 4 2 8“ a seřaďte pole od nejnižšího číslo na největší číslo pomocí třídění bublin. V každém kroku se porovnávají prvky psané tučně. Budou vyžadovány tři průchody;
První průchod (5 1 4 2 8) → (1 5 4 2 8), Zde algoritmus porovnává první dva prvky a prohodí od 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Zaměnit od 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Zaměnit od 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nyní, protože tyto prvky jsou již v pořádku (8 > 5), algoritmus je nevymění. Druhý průchod (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Zaměnit od 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)
Nyní je pole již seřazeno, ale algoritmus neví, zda je dokončeno . Algoritmus potřebuje jeden celý průchod bez jakéhokoli swapu, aby věděl, že je seřazen.