Гномья сортировка

Гномья сортировка

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков

Алгоритм

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Алгоритм концептуально простой, не требует вложенных циклов. Время работы O(n^2). На практике алгоритм может работать также быстро, как и сортировка вставками.

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.

Реализация гномьей сортировки на С++

01	//Гномья сортировка

02

03	void gnomeSort(a[0..size - 1])

04

{

05

i = 1;

06

j = 2;

07	while i < size

08	if a[i - 1] =

09

i = j;

10	j = j + 1;

11

else

12	swap a[i - 1] and a[i]

13	i = i - 1;

14

if i == 0

15

i = j;

16	j = j + 1;

17

18

}

19	/******************/

Пример

Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:

• [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] и a[0], сейчас i == 3, j == 4);
• [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
• [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
• цикл закончился, т. к. i не < 4.