Гномья сортировка массива на Ассемблере

Гномья сортировка - один из методов сортировки данных, сочетающий в себе элементы алгоритмов сортировки пузырьком и сортировки вставками. Такое необычное название алгоритм получил благодаря голландскому ученому Дику Груну, детально исследовавшему этот метод сортировки. Вот как он описывает гномью сортировку в своих работах:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. Он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперед, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперед; если нет следующего горшка, он закончил.

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Сортировка простая, не требует вложенных циклов и вспомогательных массивов, все данные сортируются за один проход.

Благодаря своей простоте, алгоритм гномьей сортировки легко реализуется практически на любом языке программирования. Вот мой вариант функции сортировки на Ассемблере:Параметры вызова: lpArray - указатель на массив DWORD, который необходимо отсортировать, dLen - количество элементов в массиве, должно быть не менее двух. После отработки исходный массив будет отсортирован. Порядок сортировки определяется условным переходом, в приведенных примерах это сортировка по возрастанию. Для сортировки массива по убыванию замените в обозначенном месте условный переход JBE на JAE.

Сортировку можно заметно ускорить, если запоминать индекс крайнего неотсортированного элемента. После того как сделан ряд шагов назад, дальнейшую обработку массива необходимо продолжить с того места, где прервались. Я немного модифицировал предыдущую функцию, в результате получилась оптимизированная функция гномьей сортировки:В приложении примеры программ с исходными текстами, сортирующие массив по возрастанию с помощью обычного и оптимизированного алгоритма.

Комментарии

Добавить комментарий

Для вставки цитаты выделите текст и нажмите сюда

Имя*:

Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.

Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.