Сортировка Шелла на Ассемблере

Сегодня разберем еще один алгоритм сортировки - сортировку Шелла. Он назван в честь ученого Дональда Шелла, который в 1959 году опубликовал этот алгоритм. Сортировка Шелла представляет собой нечто среднее между классической пузырьковой сортировкой и сортировкой вставками, легко реализуется на разных языках программирования, при этом показывает хорошую скорость работы и не требует выделения дополнительной памяти.

Суть алгоритма сортировки Шелла заключается в сравнении элементов последовательности, разделенных на группы и находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N - общее число элементов сортируемого массива. На первом шаге каждая группа включает в себя два элемента, расположенных друг от друга на расстоянии N/2. Они сравниваются между собой, и, в зависимости от направления сортировки, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, а количество групп, соответственно, уменьшается. Постепенно расстояние между сравниваемыми элементами уменьшается, и на d=1 проход по массиву происходит в последний раз. Вот как это выглядит на Ассемблере:В приложении пример программы с исходным текстом, которая сортирует массив по алгоритму Шелла.

Комментарии

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

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

Имя*:

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

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

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