Sortowanie gnoma (ang. gnome sort) – algorytm sortowania podobny 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 (), który zamienia miejscami doniczki w ogrodzie.
Algorytm wyróżnia się prostotą, nie zawiera zagnieżdżonych pętli. Algorytm wykonuje co najmniej tyle samo porównań co sortowanie przez wstawianie i ma takie samo asymptotyczne tempo wzrostu. Jego złożoność obliczeniowa to O(n2) 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).
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.
Przypisy
Linki zewnętrzne Gnome sort
Gnoma