Гном сорт

Гном сорт (Шаблон:Јез-ен) или Глупи сорт (Шаблон:Јез-ен), представио га је 2000. године Хамид Сарбази-Азад и назвао га Глупи сорт. Касније га је додатно описао Дик Грун и назвао га Гном сорт. Гном сорт представља једноставан алгоритам за сортирање сличан алгоритму сортирање уметањем. Разлика је у томе што се елемент доводи на своје место низом премештања, слично сортирању са мехурима (Шаблон:Јез-ен). У суштини је прост алгоритам, без угњеждених петљи. Време извршавања је $O(n^2)$ , али тежи $O(n)$ ако је низ иницијално скоро сортиран. У пракси алгоритам може да ради истом брзином као сортирање уметањем.

Алгоритам увек налази прву позицију на којој су два суседна елемента у погрешном редоследу и замени их. Затим искоришћава чињеницу да замена елемената може да произведе нов пар суседа у погрешном редоследу и то само непосредно пре или после замењених елемената. Алгоритам не претпоставља да ли су елементи после текуће позиције сортирани, па мора само да провери позицију пре текуће.

Визуализација рада Гном сорт алгоритма

Сложеност

• Структура података: низ
• Временска сложеност најгорег случаја: $O(n^2)$
• Временска сложеност просечног случаја: $O(n^2)$
• Временска сложеност најбољег случаја: $O(n)$
• Просторна сложеност најгорег случаја: $O(1)$

Опис алгоритма

Испод је дат псеудокод алгоритма

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

Пример

Дат је несортиран низ а = [5, 3, 2, 4]. „Тренурна позиција“ је означена подебњаним цифрама. Ово су кораци које гном сорт алгоритам извршава:

Тренутни низ	Тренутна операција
[5, 3, 2, 4]	a[позиција] < a[позиција-1], размени:
[3, 5, 2, 4]	a[позиција] >= a[позиција-1], увећај позиција:
[3, 5, 2, 4]	a[позиција] < a[позиција-1], размени и позиција > 1, умањи позиција:
[3, 2, 5, 4]	a[позиција] < a[позиција-1], размени и позиција <= 1, увећај позиција:
[2, 3, 5, 4]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 5, 4]	a[позиција] < a[позиција-1], размени и позиција > 1, умањи позиција:
[2, 3, 4, 5]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 4, 5]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 4, 5]	позиција == дужинаНиза(a), КРАЈ.

C++ имплементација

Ово је генеричка имплементација која имитира шаблон стандардне C++ сорт функције. Ова функција прерађена тако да може да ради са C низовима, C++11 низовима, редовима, листама и векторима.

#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;
            }
        }
}

Спољашње везе

• Гном сорт