Гномья сортировка :: 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 on Wikipedia
Гномья сортировка в Википедии
Реализация на различных ЯП

Добавить комментарий