Відкрити головне меню


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

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

АналізРедагувати

ШвидкодіяРедагувати

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

Приклад використання крок за крокомРедагувати

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

Можлива оптимізаціяРедагувати

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

ПосиланняРедагувати