Алгоритмы. Урок 3. Алгоритм гномьей сортировки (while, var, циклы в Delphi) |
Автор megabax | ||
20.05.2010 г. | ||
Алгоритм гномьей сортировки (while, var, циклы в Delphi)Тестовый пример для сравнения пузырьковой и гномьей сортировки можете скачать здесь.
Гномья
сортировка основана на технике, используемой обычным голландским садовым
гномом (нидерл. tuinkabouter).
Это метод, которым садовый гном сортирует линию цветочных горшков. По
существу он смотрит на следующий и предыдущий садовые горшки: если они в
правильном порядке, он шагает на один горшок вперёд, иначе он меняет их
местами и шагает на один горшок назад. Граничные условия: если нет
предыдущего горшка, он шагает вперёд; если нет следующего горшка, он
закончил. Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов. Вот как такая процедура будет выглядеть на Delphi:
Работу этого алгоритма мы рассмотрим на примере сортировки последовательности чисел [424] [206] [849] [925] [854].
Тестовый пример для сравнения пузырьковой и гномьей сортировки можете скачать здесь.
Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями программного продукта "Delphi", авторское право на который принадлежит Borland Delphi.. |
||
Последнее обновление ( 10.02.2013 г. ) |
« След. | Пред. » |
---|