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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування гнома
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія O(n^2)
Найкраща швидкодія O(n)
Середня швидкодія O(n^2)

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

Аналіз[ред.ред. код]

Швидкодія[ред.ред. код]

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

Приклад реалізації на C++[ред.ред. код]

#include <algorithm>
 
template<class T>
void gnomeSort(T* a, int n)
{
    for (int i = 0; i < n; )
    {
        if (i == 0 || a[i - 1] <= a[i])
        {
            ++i;
        }
        else
        {
            std::swap(a[i], a[i - 1]);
            -- i;
        }
    }
}

Можлива оптимізація[ред.ред. код]

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

Посилання[ред.ред. код]