Гномья сортировка (оптимизированная) :: Gnome Sort (optimization)

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

Оптимизация для гномьей сортировки

Алгоритм

В обычной гномьей сортировке происходит просмотр массива слева-направо, при этом сравниваются (и меняются, если это неотсортированная пара) соседние элементы. Если происходит обмен элементов, то проиходит возвращение на один шаг назад. Если обменов не происходит, то алгоритм продолжает просмотр массива слева-направо в поиске неотсортированных пар.

Оптимизация

Оптимизация заключается в том, что при обмене запоминается позиция в массиве, на которой этот обмен произошёл. При подряд нескольких обменах приходится делать столько же шагов назад. Затем приходится возвращаться обратно (сравнивая по пути элементы, которые и так упорядочены друг относительно друга). Если запоминать позицию, с которой начались обмены, то затем можно сразу же вернуться в эту позицию, когда обмены завершены.

Характеристики алгоритма

НазваниеГномья сортировка (Gnome sort)
АвторыХамид Сарбази-Асад (Hamid Sarbazi-Azad); Дик Грун (Dick Grune)
Год2000
КлассСортировки обменами
УстойчивостьУстойчивая
СравненияДа
Сложность по времениЛучшаяO(n)
СредняяO(n2)
ХудшаяO(n2)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Гномья сортировка (оптимизированная) на Python

Гномья сортировка (оптимизированная) на PHP

Ссылки

Сортировки обменами

Глупая сортировка и некоторые другие, поумнее

Gnome sort

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

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