Bublinkové řazení

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

Bublinkové řazení (známé pod anglickým jménem 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

Ukázka algoritmu na řazení množiny čísel. Červeně jsou ohraničeny právě porovnávané dvojice. Černě jsou ohraničeny již seřazené prvky.

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, je horší i ve srovnání s jinými algoritmy se stejnou asymptotickou složitostí, neboť vyžaduje velké množství zápisů do paměti a tím neefektivně pracuje s cache procesoru.

Díky své jednoduché implementaci se však často objevuje v úvodních kurzech programování.

Výhody a nevýhody

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

Bublinkové řazení se používá například pro výuku programování, nebo pro řazení malých polí, nebo polí, která jsou již částečně seřazena. 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 řazení opravdu velkých polí je bublinkové řazení naprosto nevhodné. Pokud např. seřazení desetiprvkového pole trvá jednotku času, pak při bublinkovém řazení stokrát delšího (tisíciprvkového pole) spotřebujeme 10000 jednotek času, zatímco kvalitní algoritmus by potřeboval pouze 200 jednotek času^[zdroj?].

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á koktejlové řazení.

Externí odkazy

Obrázky, zvuky či videa k tématu bublinkové řazení na Wikimedia Commons