Stooge sort

O(n^2.71)

Stooge sort prohodí konce, pokud jsou ve špatném pořadí, a pak rekurzivně seřadí první dvě třetiny, poslední dvě třetiny a znovu první dvě třetiny. Je správný, ale nádherně neefektivní — zhruba O(n^2.71) — učebnicový příklad, jak může rozumně vypadající rekurze být příšerná.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Když je první prvek větší než poslední, prohoď je.
  2. Rekurzivně seřaď první dvě třetiny rozsahu.
  3. Rekurzivně seřaď poslední dvě třetiny.
  4. Rekurzivně seřaď první dvě třetiny ještě jednou.

Pseudokód

1stoogeSort(a, lo, hi):              # O(n^2.71)2  if a[lo] > a[hi]: swap(a[lo], a[hi])3  if hi - lo + 1 > 2:4    t ← (hi - lo + 1) / 35    stoogeSort(a, lo, hi-t)          # first two-thirds6    stoogeSort(a, lo+t, hi)          # last two-thirds7    stoogeSort(a, lo, hi-t)          # first two-thirds again