Гномья сортировка :: 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

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

Реализация на различных ЯП