|
|
Сортировка методом Шелла (сортировка с убывающим шагом, D. L. Shell)
Модификация сортировки простыми вставками.
Шаг 1. Упорядочиваемое множество разбивается на несколько непересекающихся подмножеств по следующему правилу:
берутся элементы неупорядоченного множества, расположенные на одинаковом расстоянии (дистанции) друг от друга. Полученные множества сортируются методом простых вставок, что позволяет уменьшить общую неупорядоченность множества.
Шаг 2. Алгоритм завершает работу, когда дистанция равна 1, иначе уменьшается дистанция между элементами и повторяется шаг 1.
Примечание:
Выбор последовательности дистанций между элементами в сортировке методом Шелла является отдельной проблемой, которая подробно рассматривается Д.Кнутом в монографии “Искусство программирования для ЭВМ. Т.3: Сортировка и поиск”.
Характеристики алгоритма:
Эффективный алгоритм для почти упорядоченного множества.
Эффективный алгоритм для небольшого количества элементов.
Устойчивая сортировка.
Сложность зависит от последовательности дистанций между элементами и изменяется от  до 
Интересно поведение этого алгоритма в зависимости от выбора значения дистанции.
|
|
