Koktejlové řazení

Koktejlové řazení (anglicky shaker sort, či též cocktail sort) je implementačně jednoduchý řadicí algoritmus, vycházející z algoritmu bublinkového řazení.

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. Od bublinkového řazení se liší tím, že prochází seznam v obou směrech. Tedy od začátku seznamu ke konci a poté zpět. Tímto postupem se předejde nevýhodě bublinkového řazení, tzv. problému želv a zajíců. Problém spočívá v tom, že vysoké hodnoty probublají na konec pole rychle, ale ty nízké postupují na začátek velmi pomalu. Porovnávání prvků běží do té doby, dokud není seznam seřazený. Pro praktické účely je algoritmus neefektivní. Využívá se hlavně pro výuku č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 „probubláváme“ seznam na konec a zase zpět.

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

Časová složitost

Přestože se zmenšil počet zbytečných porovnání (viz výše zmíněný problém želv a zajíců), tak asymptotická složitost zůstává stejná. Průměrná i nejhorší asymptotická složitost koktejlového řazení je ${\displaystyle 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.