Сортування гнома — Вікіпедія

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

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

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

Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна ${\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;

} ^[1]

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

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

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2017)

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