Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Описание

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• отсутствие потребности в памяти под стек;
• отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

История

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году. В некоторых старых пособиях этот алгоритм назывался Сортировка Шелл-Мецнер, в честь Марлен Мецнер-Нортон^{[источник не указан 638 дней]}. Однако, впоследствии, сама Мецнер опровергла это: «Я не имею ничего общего с этой сортировкой, и моё имя никогда не должно связываться с ней»^{[источник не указан 638 дней]}.

Пример

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

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Выбор длины промежутков

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

• первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит ;
• предложенная Хиббардом последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью ;
• предложенная Седжвиком последовательность: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: , а в худшем случае порядка . При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.^[1];
• предложенная Праттом последовательность: все значения ; в таком случае сложность алгоритма составляет ;
• эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.^[2];
• эмпирическая последовательность, основанная на числах Фибоначчи: ;
• все значения ^{[источник не указан 1042 дня]}, ; такая последовательность шагов приводит к алгоритму сложностью .

Примечания

1. ↑ J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
2. Marcin Ciura Best Increments for the Average Case of Shellsort