Bublinkové řazení

Ilustrace bublinkového řazení množiny náhodných čísel

Bublinkové řazení (anglicky bubble sort, česky též řazení záměnou) je implementačně jednoduchý řadicí algoritmus. Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely či v nenáročných aplikacích.

Algoritmus je univerzální (pracuje na základě porovnávání dvojic prvků), pracuje lokálně (nevyžaduje pomocnou paměť), je stabilní (prvkům se stejným klíčem nemění vzájemnou polohu), patří mezi přirozené řadicí algoritmy (částečně seřazený seznam zpracuje rychleji než neseřazený).

Název vyjadřuje průběh zpracování, při kterém prvky s vyšší hodnotou „probublávají“ na konec seznamu.

Optimalizací algoritmu je detekce prohození prvků v průchodu seznamu. V případě, že algoritmus v průchodu neprohodil žádné dva prvky, tak žádné další prvky již nikdy neprohodí. Tudíž řazení můžeme ukončit s tím, že seznam je seřazen.

Algoritmus

Poznámka: toto je jen jedna z mnoha variací algoritmu.

opakuj
bylo_seřazeno := ano;
pro i od 1 do (počet_prvků - 1) opakuj:
pokud seznam[i] > seznam[i + 1]
zaměň(seznam[i], seznam[i + 1])
bylo_seřazeno := ne;
dokud není bylo_seřazeno == ano;

Alternativní verze:

limit := počet_prvků;
opakuj
bylo_seřazeno := ano;
limit := limit - 1;
pro i od 1 do limit opakuj:
pokud seznam[i] > seznam[i + 1]
zaměň(seznam[i], seznam[i + 1])
bylo_seřazeno := ne;
dokud není bylo_seřazeno == ano nebo limit == 1;

Výhodou alternativní verze je o něco vyšší efektivita. Po n opakováních je spodních n prvků již seřazeno a je zbytečné je znovu procházet. Další výhodou je, že upravený algoritmus se nezacyklí v nekonečné smyčce ani v případě, že bychom měli špatně implementovanou funkci pro porovnávání prvků seznamu.

Časová složitost

Průměrná i nejhorší asymptotická složitost bublinkového řazení je $O(n^2)$.

Tento algoritmus řazení je jedním z nejpomalejších, oproti jiným algoritmům se stejnou složitostí vyžaduje velké množství zápisů do paměti a tím neefektivně pracuje s cache procesoru.

Výhody a nevýhody

Bublinkové řazení je z hlediska naprogramování nejjednodušším algoritmem pro třídění. Výhodou rovněž je, že je stabilní, tzn. nemění pozici prvků které jsou při porovnávání vyhodnoceny jako ekvivalentní. Bublinkové třídění je jeden z mála třídících algoritmů, kterému stačí sekvenční přístup k datům (algoritmus nepotřebuje ve tříděné posloupnosti provádět žádné skoky). V minulosti se proto používal ke třídění dat na páskových médiích, dnes jej lze s výhodou použít například při třídění jednosměrně zřetězeného spojového seznamu.

Bublinkové třídění se používá například pro výuku programování, nebo pro třídění malých polí, nebo polí která jsou již částečně setříděna. Vzhledem k vysokému výkonu současných počítačů může mít "malé" pole i několik tisíc prvků, avšak pro třídění opravdu velkých polí je "bubblesort" naprosto nevhodný. Pokud trvá setřídění např. 10 prvků dlouhého pole jednotku času, pak při bublinkovém třídění 1000 prvků spotřebujeme 10000 jednotek času, zatímco při použití kvalitního algoritmu pouze 200 jednotek času.

Další nevýhodou jsou zbytečná porovnání při řazení seznamu s nejnižším prvkem na konci (pokud uvažujeme vzestupné řazení). V tomto případě nepomůže ani optimalizace pomocí detekce prohození prvků, jelikož tento nejnižší prvek se v každém průchodu posune pouze o jedno místo vlevo. Tento problém řeší modifikace algoritmu nazvaná Shaker sort.