Гномья сортировка
Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.
![]() | Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил. Дик Грун | ![]() |
Алгоритм концептуально простой, не требует вложенных циклов. Время работы . На практике алгоритм может работать так же быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.
Описание[править | править код]
Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишних итераций и сравнений:
gnomeSort(a[0..size - 1]) i = 1; j = 2; while i < size if a[i - 1] > a[i] //для сортировки по возрастанию поменяйте знак сравнения на < i = j; j = j + 1; else swap a[i - 1] and a[i] i = i - 1; if i == 0 i = j; j = j + 1;
Пример:
Если мы хотим отсортировать массив с элементами [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.
Оптимизация[править | править код]
В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.
Ссылки[править | править код]
- Описание метода и листинг программ гномьей сортировки.