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


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

Сортування гнома
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія
Найкраща швидкодія
Середня швидкодія

Аналіз

Швидкодія

Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна , однак, на практиці, може працювати й швидше у режимі сортування вставками.

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

Відсортуємо масив числових елементів [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]

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

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

Посилання


  1. Gnome Sort. GeeksforGeeks (амер.). 27 червня 2016. Процитовано 23 квітня 2020.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.