Гном сорт

Из Википедије, слободне енциклопедије

Гном сорт (енгл. Gnome sort) или Глупи сорт (енгл. Stupid sort), представио га је 2000. године Хамид Сарбази-Азад и назвао га Глупи сорт.[1] Касније га је додатно описао Дик Грун и назвао га Гном сорт[2]. Гном сорт представља једноставан алгоритам за сортирање сличан алгоритму сортирање уметањем. Разлика је у томе што се елемент доводи на своје место низом премештања, слично сортирању са мехурима ((енгл. Bubble sort). У суштини је прост алгоритам, без угњеждених петљи. Време извршавања је O(n^2) , али тежи O(n) ако је низ иницијално скоро сортиран.[3] У пракси алгоритам може да ради истом брзином као сортирање уметањем.


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

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

Сложеност[уреди]

  • Структура података: низ
  • Временска сложеност најгорег случаја: 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;
            }
        }
}


Референце[уреди]

  1. ^ http://sina.sharif.edu/~azad/stupid-sort.PDF
  2. ^ Gnome Sort - The Simplest Sort Algorithm
  3. ^ Paul E. Black. „gnome sort“. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology Приступљено 20. 8. 2011.. 

Спољашње везе[уреди]