Bubble sort

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

Bubble sort (v překladu bublinkové řazení, 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. Porovnávání prvků běží do té doby, dokud není seznam seřazený. 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ý).

Pracuje opakovaným přechodem přes seznam, přičemž porovnává dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený. Název vyjadřuje průběh zpracování, při kterém prvky s vyšší hodnotou „probublávají“ na konec seznamu.

[editovat] 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;

[editovat] Časová složitost

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

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 praxi se nepoužívá, často slouží jako algoritmus používaný pro výuku programování.