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