Сортування гнома () — один із найпростіших алгоритмів сортування (на думку багатьох — найпростіший). Ім'я походить від голландського садового гнома, якого ставлять між квітковими горщиками. Якщо два сусідні від гнома горщики йдуть у правильному порядку, гном йде на одну позицію вперед. Якщо ж вони у неправильному порядку — міняє ці два горщики місцями і йде на одну позицію назад (щоб знову перевірити порядок).
Аналіз
Швидкодія
Алгоритм концептуально простий, і не потребує навіть вкладених циклів. Його швидкодія рівна , однак, на практиці, може працювати й швидше у режимі сортування вставками.
Приклад використання крок за кроком
Відсортуємо масив числових елементів від найбільшого до найменшого: (ініціалізація. i = 1, а j = 2.) (нічого не робити, однак, тепер i = 2, а j = 3.) (міняємо місцями a та a. однак, тепер i = 1, а j й досі = 3.) (міняємо місцями a and a. однак, тепер i = 1, а j й досі = 3.) (нічого не робити, однак, тепер i = 3, а j = 4.) (міняємо місцями a and a. однак, тепер i = 2, а j = 4.) (нічого не робити, однак, тепер 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;
Можлива оптимізація Можна ввести додаткову змінну для запам'ятовування позиції гнома до того, як він почав рух назад. Завдяки ній, гном після впорядкування (і переміщення назад) зможе телепортуватися на цю позицію, з якої почав свій рух назад.
Посилання Gnome sort RosettaCode.org: Реалізація алгоритму різними мовами програмування