Сортировка Шелла является довольно интересной модификацией алгоритма
сортировки простыми вставками.
Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].

1. Вначале сортируем простыми вставками каждые 8 групп
из 2-х элементов (a[0], a[8[), (a[1], a[9]),..., (a[7], a[15]).

2. Потом сортируем каждую из четырех групп по 4 элемента
(a[0], a[4], a[8], a[12]),..., (a[3], a[7], a[11], a[15]).

В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.
3. Далее сортируем 2 группы по 8 элементов, начиная
с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

4. В конце сортируем вставками все 16 элементов.

Очевидно, лишь последняя сортировка необходима, чтобы расположить
все элементы по своим местам.
Hа самом деле они продвигают элементы максимально близко к
соответствующим позициям, так что в последней стадии число
перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.
Единственной характеристикой сортировки Шелла является приращение –
расстояние между сортируемыми элементами, в зависимости от прохода.
В конце приращение всегда равно единице - метод завершается
обычной сортировкой вставками, но именно последовательность
приращений определяет рост эффективности.
|