Gnome sort

O(n²)

Gnome sort používá jediný index: když je aktuální dvojice ve správném pořadí, jde vpřed, jinak ji prohodí a couvne zpět. V podstatě je to insertion sort dělaný prohozeními bez vnořeného cyklu — jednoduchý na popis, O(n²), hlavně pro výuku.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Podívej se na aktuální prvek a ten před ním.
  2. Pokud jsou ve správném pořadí (nebo jsi na začátku), posuň se o pozici vpřed.
  3. Pokud ne, prohoď je a posuň se o pozici zpět.
  4. Opakuj, dokud index nepřejede za konec.

Pseudokód

1gnomeSort(a):                       # O(n²)2  i ← 03  while i < n:4    if i = 0 or a[i-1] ≤ a[i]:5      i ← i + 1                       # step forward6    else:7      swap(a[i-1], a[i]); i ← i - 1   # swap and step back