Comb sort

O(n² / 2^p)

Comb sort zrychluje bubble sort tím, že nejdřív porovnává prvky daleko od sebe (velká mezera) a mezeru každé kolo zmenší zhruba 1,3× až na 1. Velké mezery na začátku rychle odstraní malé hodnoty uvízlé u konce, takže poslední téměř-bubble průchod už nemá moc práce.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni s mezerou velkou jako celé pole.
  2. Porovnávej a prohazuj prvky takhle daleko od sebe, zleva doprava.
  3. Mezeru zmenši (vyděl ~1,3) a opakuj.
  4. Když je mezera 1 a průchod neudělá žádné prohození, je pole seřazené.

Pseudokód

1combSort(a):                        # O(n² / 2^p)2  gap ← n; swapped ← true3  while gap > 1 or swapped:4    gap ← max(1, floor(gap / 1.3))   # shrink the gap5    swapped ← false6    for i from 0 while i+gap < n:7      if a[i] > a[i+gap]: swap; swapped ← true