Sortowanie gnoma

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sortowanie gnoma
Sorting gnomesort anim.gif
Przykład działania sortowania gnoma
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa
Pamięciowa

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 (niderl. 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(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). W praktyce algorytm działa równie szybko jak algorytm sortowania przez wstawianie, chociaż wiele zależy od struktury programu i implementacji.

Pseudokod[edytuj]

 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[edytuj]