Cocktail sort

O(n²)

Cocktail sort (obousměrný bubble sort) střídá směr: jeden průchod probublá největší hodnotu na konec, další probublá nejmenší na začátek. Tím rychleji vyřeší malé hodnoty uvízlé u konce („želvy“) než obyčejný bubble sort, i když je pořád O(n²).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Projdi zleva doprava a prohazuj sousední dvojice ve špatném pořadí — největší probublá na konec.
  2. Projdi zprava doleva stejně — nejmenší probublá na začátek.
  3. Po každé dvojici průchodů zmenši neseřazenou část z obou stran.
  4. Skonči, když celé kolo neudělá žádné prohození.

Pseudokód

1cocktailSort(a):                    # O(n²)2  lo ← 0; hi ← n-1; swapped ← true3  while swapped and lo < hi:4    swapped ← false5    for j from lo to hi-1:           # forward pass6      if a[j] > a[j+1]: swap; swapped ← true7    hi ← hi - 18    for j from hi down to lo+1:      # backward pass9      if a[j-1] > a[j]: swap; swapped ← true10    lo ← lo + 1