Перегляд вихідного коду сторінки Сортування гнома

{{Картка_алгоритм
|клас=[[Алгоритм сортування]]
|зображення= [[Файл:Sorting gnomesort anim.gif|350px]]
|дані=[[Масив (структура даних)|Масив]]
|час=<math>O(n^2)</math>
|найкращий час=<math>O(n)</math>
|середній час= <math>O(n^2)</math>
|пропуски=
|оптимальний=
}}
 

'''Сортування гнома''' ({{lang-en|Gnome sort}})&nbsp;— один із найпростіших алгоритмів сортування (на думку багатьох&nbsp;— найпростіший). Ім'я походить від [[Голландія|голландського]] садового гнома, якого ставлять між квітковими горщиками. Якщо два сусідні від гнома горщики йдуть у правильному порядку, гном йде на одну позицію вперед. Якщо ж вони у неправильному порядку - міняє ці два горщики місцями і йде на одну позицію назад (щоб знову перевірити порядок).

== Аналіз ==

=== Швидкодія ===

Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна <math>O(n^2)</math>, однак, на практиці, може працювати й швидше у режимі [[сортування вставками]].

=== Приклад використання крок за кроком ===

Відсортуємо масив числових елементів [4] [2] [7] [3] від найбільшого до найменшого:<br/>
[4] [2] [7] [3] (ініціалізація. i = 1, а j = 2.)<br/>
[4] [2] [7] [3] (нічого не робити, однак, тепер i = 2, а j = 3.)<br/>
[4] [7] [2] [3] (міняємо місцями a[2] та a[1]. однак, тепер i = 1, а j й досі = 3.)<br/>
[7] [4] [2] [3] (міняємо місцями a[1] and a[0]. однак, тепер i = 1, а j й досі = 3.)<br/>
[7] [4] [2] [3] (нічого не робити, однак, тепер i = 3, а j = 4.)<br/>
[7] [4] [3] [2] (міняємо місцями a[3] and a[2]. однак, тепер i = 2, а j = 4.)<br/>
[7] [4] [3] [2] (нічого не робити, однак, тепер i = 4, а j = 5.)<br/>
на цьому місці цикл завершується, оскільки і не < 4.<br/>

== Реалізація ==

Алгоритм можна записати в [[псевдокод]]і:

  '''function''' gnomeSort(a[0..size-1]) {
   i := 1
   j := 2
   '''while''' i < size
     '''if''' a[i-1] <= a[i] ''# для сортування в спадаючому порядку замінити на &ge;''
         i := j
         j := j + 1 
     '''else'''
         переставити a[i-1] та a[i]
         i := i - 1
         '''if''' i = 0
           i = j;
           j = j + 1;
  }
C++:

<code>void</code> <code>gnomeSort(int</code> <code>arr[], int</code> <code>n)</code> 

<code>{</code>

<code>   int</code> <code>index = 0;</code> 

 

<code>   while</code> <code>(index < n) {</code>

<code>       if</code> <code>(index == 0)</code>

<code>           index++;</code>

<code>       if</code> <code>(arr[index] >= arr[index - 1])</code>

<code>           index++;</code>

<code>       else</code> <code>{</code>

<code>           swap(arr[index], arr[index - 1]);</code>

<code>           index--;</code>

<code>       }</code>

<code>   }</code>

<code>   return;</code> 

<code>}</code> <ref>{{Cite web|title=Gnome Sort|url=https://www.geeksforgeeks.org/gnome-sort-a-stupid-one/|website=GeeksforGeeks|date=2016-06-27|accessdate=2020-04-23|language=en-US}}</ref>

== Можлива оптимізація ==
Можна ввести додаткову змінну для запам'ятовування позиції гнома до того, як він почав рух назад. Завдяки ній, гном після впорядкування (і переміщення назад) зможе телепортуватися на цю позицію, з якої почав свій рух назад.

== Посилання ==
*[https://www.geeksforgeeks.org/gnome-sort-a-stupid-one/ Gnome sort]
* RosettaCode.org: [http://rosettacode.org/wiki/Sorting_algorithms/Gnome_sort#Common_Lisp Реалізація алгоритму різними мовами програмування]


{{Algorithm-stub}}
{{Refimprove|дата=грудень 2017}}
{{Алгоритми сортування}}
{{ВП-портали|Програмування|Інформаційні технології}}

[[Категорія:Алгоритми сортування]]