Cycle sort

O(n²)

Cycle sort spočítá, kam přesně hodnota patří (kolik prvků je menších), a zapíše ji přímo tam — vytlačí to, co tam bylo, a tu hodnotu pak umístí stejně, čímž vznikne „cyklus“. V počtu porovnání je O(n²), ale dělá nejmenší možný počet zápisů, což se hodí, když je zápis drahý (např. flash paměť).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Pro aktuální start spočítej, kolik hodnot je menších — to je jeho konečná pozice.
  2. Zapiš hodnotu tam a zvedni to, co vytlačí.
  3. Vytlačenou hodnotu umísti stejně a pokračuj v cyklu, dokud se nevrátí na start.
  4. Posuň se na další startovní pozici a opakuj.

Pseudokód

1cycleSort(a):                       # O(n²), minimal writes2  for start = 0 to n-2:3    item ← a[start]4    pos ← start + (count of a[i] < item, for i > start)5    if pos = start: continue         # already in place6    while item = a[pos]: pos++        # skip duplicates7    swap item with a[pos]             # place it, pick up the next8    repeat until the cycle returns to start