Sortowanie gnoma
Szablon:Algorytm infobox 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 (Szablon:W języku), który zamienia miejscami doniczki w ogrodzie[1].
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)[2].
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.