Сортування гнома

Сортування гнома (англ. Gnome sort) — один із найпростіших алгоритмів сортування (на думку багатьох — найпростіший). Ім'я походить від голландського садового гнома, якого ставлять між квітковими горщиками. Якщо два сусідні від гнома горщики йдуть у правильному порядку, гном йде на одну позицію вперед. Якщо ж вони у неправильному порядку - міняє ці два горщики місцями і йде на одну позицію назад (щоб знову перевірити порядок).

Сортування гнома

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	${\displaystyle O(n^{2})}$
Найкраща швидкодія	${\displaystyle O(n)}$
Середня швидкодія	${\displaystyle O(n^{2})}$

Аналіз

Швидкодія

Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна ${\displaystyle O(n^{2})}$, однак, на практиці, може працювати й швидше у режимі .

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

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

Реалізація

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

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

C++:

void gnomeSort(int arr[], int n)

{

   int index = 0;

 

   while (index < n) {

       if (index == 0)

           index++;

       if (arr[index] >= arr[index - 1])

           index++;

       else {

           swap(arr[index], arr[index - 1]);

           index--;

       }

   }

   return;

}

Можлива оптимізація

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

Посилання

• Gnome sort
• RosettaCode.org: Реалізація алгоритму різними мовами програмування

1. Gnome Sort. GeeksforGeeks (амер.). 27 червня 2016. Процитовано 23 квітня 2020.