Метод Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма

сортировки простыми вставками.

Рассмотрим следующий алгоритм сортировки массива 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а самом деле они продвигают элементы максимально близко к

соответствующим позициям, так что в последней стадии число

перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.

Единственной характеристикой сортировки Шелла является приращение –

расстояние между сортируемыми элементами, в зависимости от прохода.

В конце приращение всегда равно единице - метод завершается

обычной сортировкой вставками, но именно последовательность

приращений определяет рост эффективности.