Сортировка Шелла. 
Теоретические основы информатики

Сортировка, предложенная Да Шеллом (англ. Shell sort) в 1959 г., является обобщением алгоритма сортировки вставками.

Разобьем упорядочиваемое множество А = {ai, a2,…, а_п} на группы элементов, расположенные друг от друга на расстоянии d = [п/2], где [ ] — целая часть числа, и сравним последовательно пары элементов а и ^а2 и a-2+d и т. д. Если а, — > а*₊₍*, то а, — и a_i+d меняются местами. После сравнения и упорядочивания всех пар выбирают новое расстояние d = [d/2] и процесс повторяется снова.

На некотором шаге получим d = 1 — это аналог сортировки вставкой. Выполнив ее, будем иметь упорядоченное по возрастанию множество А.

Пример 11.4. Используя алгоритм сортировки Шелла, упорядочить множество чисел А = {9,3,12,1,8,5} по возрастанию.

Решение. Состояния множества А при сортировке Шелла приведены в табл. 11.3.

Сортировка Шелла

Таблица 11.3

Алгоритм останавливается при достижении состояния так как все элементы упорядочены. ?

Сложность алгоритма сортировки Шелла зависит от выбора последовательности значений расстояния d. Указанный выше алгоритм выбора d был предложен Шеллом, в этом случае алгоритм имеет сложность порядка 0(п²).

Существуют и другие подходы к выбору d. Например, можно использовать последовательность значений d = 2* — 1, где d ^ гг, к — натуральное число. При этом сложность алгоритма снижается до порядка 0(п³^²).