Гном сорт () или Глупи сорт (), представио га је 2000. године Хамид Сарбази-Азад и назвао га Глупи сорт. Касније га је додатно описао Дик Грун и назвао га Гном сортGnome Sort - The Simplest Sort Algorithm. Гном сорт представља једноставан алгоритам за сортирање сличан алгоритму сортирање уметањем. Разлика је у томе што се елемент доводи на своје место низом премештања, слично сортирању са мехурима (). У суштини је прост алгоритам, без угњеждених петљи. Време извршавања је , али тежи ако је низ иницијално скоро сортиран. У пракси алгоритам може да ради истом брзином као сортирање уметањем.
Алгоритам увек налази прву позицију на којој су два суседна елемента у погрешном редоследу и замени их. Затим искоришћава чињеницу да замена елемената може да произведе нов пар суседа у погрешном редоследу и то само непосредно пре или после замењених елемената. Алгоритам не претпоставља да ли су елементи после текуће позиције сортирани, па мора само да провери позицију пре текуће. мини|десно|Визуализација рада Гном сорт алгоритма
Сложеност Структура података: низ Временска сложеност најгорег случаја: Временска сложеност просечног случаја: Временска сложеност најбољег случаја: Просторна сложеност најгорег случаја:
Опис алгоритма Испод је дат псеудокод алгоритма
ПРОГРАМ гномСорт(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;
Референце
Спољашње везе Гном сорт
Категорија:Информатика Категорија:Алгоритми Категорија:Алгоритми сортирања Категорија:Програмирање Категорија:Стабилно сортирање