Sortowanie gnoma

Z Wikipedii

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

Działanie algorytmu jest proste, nie wymaga wielu zagnieżdżonych pętli. Czas działania wynosi O(n²). W praktyce algorytm działa równie szybko jak algorytm sortowania przez wstawianie, chociaż wiele zależy od struktury programu i implementacji.

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

[edytuj] linki

• Gnome sort
• NGenerics - implementation in C#