Sortowanie gnoma
| Ten artykuł od 2016-03 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
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
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.)