Гномья сортировка :: Gnome sort
Незамысловатый обменный алгоритм с неплохой сложностью O(n2), который, как ни парадоксально, совсем недавно был впервые описан в научной литературе.
"Новую сортировку" презентовал на страницах научного издания Newsletter Университета Глазго, некий Хамид Сарбази-Асад (Hamid Sarbazi-Azad) в 2000 году. Он предложил название "Глупая сортировка".
Голландский учёный Дик Грун (Dick Grune) исследовал метод подробнее и переименовал в "Гномью сортировку", под этим именем алгоритм сейчас и известен.
Алгоритм
"Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил."
Дик Грун
Гномья сортировка это оптимизированная глупая сортировка. В глупой сортировке при нахождении неотсортированной пары соседей происходит обмен и возврат в начало массива. В гномьей сортировке просто делается один шаг назад.
Также алгоритм интересен тем, что используется всего лищь один цикл, что для алгоритмов сортировок большая редкость.
Для гномьей сортировки существует оптимизированная версия.
Характеристики алгоритма
| Название | Гномья сортировка (Gnome sort) | |
|---|---|---|
| Авторы | Хамид Сарбази-Асад (Hamid Sarbazi-Azad); Дик Грун (Dick Grune) | |
| Год | 2000 | |
| Класс | Сортировки обменами | |
| Устойчивость | Устойчивая | |
| Сравнения | Да | |
| Сложность по времени | Лучшая | O(n) |
| Средняя | O(n2) | |
| Худшая | O(n2) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Gnome sort
Реализация на различных ЯП