- Гномья сортировка
-
Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка.
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик ГрунАлгоритм концептуально простой, не требует вложенных циклов. Время работы . На практике алгоритм может работать так же быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.
Описание
Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишних итераций и сравнений:
gnomeSort(a[0..size - 1]) i = 1; j = 2; while i < size if a[i - 1] <= a[i] //для сортировки по убыванию поменяйте знак сравнения на >= i = j; j = j + 1; else swap a[i - 1] and a[i] i = i - 1; if i == 0 i = j; j = j + 1;
Пример:
Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:
- [4] [2] [7] [3] (начальное состояние: i == 1, j == 2);
- [4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);
- [4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);
- [7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);
- [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
- [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
- цикл закончился, т. к. i не < 4.
Оптимизация
В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.