Gnom sort

Gnom sort (engl. Gnome sort) ili Glupi sort (engl. Stupid sort), predstavio ga je 2000. godine Hamid Sarbazi-Azad i nazvao ga Glupi sort. Kasnije ga je dodatno opisao Dik Grun i nazvao ga Gnom sort. Gnom sort predstavlja jednostavan algoritam za sortiranje sličan algoritmu sortiranje umetanjem. Razlika je u tome što se element dovodi na svoje mesto nizom premeštanja, slično sortiranju sa mehurima (engl. Bubble sort). U suštini je prost algoritam, bez ugnježdenih petlji. Vreme izvršavanja je $O(n^{2})$ , ali teži $O(n)$ ako je niz inicijalno skoro sortiran. U praksi algoritam može da radi istom brzinom kao sortiranje umetanjem.

Algoritam uvek nalazi prvu poziciju na kojoj su dva susedna elementa u pogrešnom redosledu i zameni ih. Zatim iskorišćava činjenicu da zamena elemenata može da proizvede nov par suseda u pogrešnom redosledu i to samo neposredno pre ili posle zamenjenih elemenata. Algoritam ne pretpostavlja da li su elementi posle tekuće pozicije sortirani, pa mora samo da proveri poziciju pre tekuće.

Vizualizacija rada Gnom sort algoritma

Složenost

• Struktura podataka: niz
• Vremenska složenost najgoreg slučaja: $O(n^{2})$
• Vremenska složenost prosečnog slučaja: $O(n^{2})$
• Vremenska složenost najboljeg slučaja: $O(n)$
• Prostorna složenost najgoreg slučaja: $O(1)$

Opis algoritma

Ispod je dat pseudokod algoritma

ПРОГРАМ гномСорт(a[])
    позиција := 1
    док је (позиција < дужинаНиза(a))
        ако (a[позиција] >= a[позиција-1])
            позиција := позиција + 1
        иначе
            размени a[позиција] и a[позиција-1]
            ако (позиција > 1)
                позиција := позиција - 1
            КРАЈ ако
        КРАЈ ако
    КРАЈ док је
КРАЈ ПРОГРАМ

Primer

Dat je nesortiran niz a = [5, 3, 2, 4]. „Trenurna pozicija“ je označena podebnjanim ciframa. Ovo su koraci koje gnom sort algoritam izvršava:

Trenutni niz	Trenutna operacija
[5, 3, 2, 4]	a[pozicija] < a[pozicija-1], razmeni:
[3, 5, 2, 4]	a[pozicija] >= a[pozicija-1], uvećaj pozicija:
[3, 5, 2, 4]	a[pozicija] < a[pozicija-1], razmeni i pozicija > 1, umanji pozicija:
[3, 2, 5, 4]	a[pozicija] < a[pozicija-1], razmeni i pozicija <= 1, uvećaj pozicija:
[2, 3, 5, 4]	a[pozicija] >= a[pozicija-1], uvećaj pozicija:
[2, 3, 5, 4]	a[pozicija] < a[pozicija-1], razmeni i pozicija > 1, umanji pozicija:
[2, 3, 4, 5]	a[pozicija] >= a[pozicija-1], uvećaj pozicija:
[2, 3, 4, 5]	a[pozicija] >= a[pozicija-1], uvećaj pozicija:
[2, 3, 4, 5]	pozicija == dužinaNiza(a), KRAJ.

C++ implementacija

Ovo je generička implementacija koja imitira šablon standardne C++ sort funkcije. Ova funkcija prerađena tako da može da radi sa C nizovima, C++11 nizovima, redovima, listama i vektorima.

#include <algorithm>

template <typename BidirectionalIterator>
void gnomeSort(BidirectionalIterator first, BidirectionalIterator last)
{
    BidirectionalIterator i = first, j = first;

    ++j;

    while (j != last)
        if (*i <= *j)
        {
            ++i;
            ++j;
        }
        else
        {
            std::iter_swap(i, j);

            if (i != first)
            {
                --i;
                --j;
            }
        }
}

Spoljašnje veze

• Gnom sort