Sortowanie gnoma

Sortowanie gnoma (ang. gnome sort) jest algorytmem sortowania podobnym do sortowania przez wstawianie. Różni go sposób przenoszenia danej na właściwe miejsce poprzez wielokrotne zamiany kolejności dwóch sąsiednich elementów, tak jak w sortowaniu bąbelkowym. Nazwa pochodzi od holenderskiego krasnala ogrodowego (hol. tuinkabouter), który zamienia miejscami doniczki w ogrodzie.

Algorytm wyróżnia się prostotą, nie zawiera zagnieżdżonych pętli. Jego złożoność obliczeniowa to O(n²) w średnim przypadku, jednak zbliża się do O(n), jeśli zbiór wejściowy jest prawie posortowany (tzn. niewielka liczba elementów jest na niewłaściwych miejscach, bądź wszystkie elementy są niedaleko swoich właściwych miejsc). W praktyce algorytm działa równie szybko jak algorytm sortowania przez wstawianie, chociaż wiele zależy od struktury programu i implementacji.

Pseudokod

 function gnomeSort(a[0..size-1]) {
  i := 1
  j := 2
  while i < size
    if a[i-1] ≤ a[i]
        i := j
        j := j + 1
    else
        swap a[i-1] and a[i]
        i := i – 1
        if i = 0
          i := 1
 }

Algorytm szybko odnajduje pierwsze miejsce, w którym dwa sąsiednie elementy są w złej kolejności i zamienia je. Istnieje ryzyko, że po przestawieniu element przed zamienioną parą zaburza porządek, jest to sprawdzane zaraz po wykonaniu zamiany.

Linki zewnętrzne

• Gnome sort (ang.)