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

Описание

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

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

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

История

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.

Пример

Пусть дан список ${\displaystyle A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)}$ и выполняется его сортировка методом Шелла, а в качестве значений ${\displaystyle d}$ выбраны ${\displaystyle 5,3,1}$.

На первом шаге сортируются подсписки ${\displaystyle A}$, составленные из всех элементов ${\displaystyle A}$, различающихся на 5 позиций, то есть подсписки ${\displaystyle A_{5,1}=(32,66,40)}$, ${\displaystyle A_{5,2}=(95,35,43)}$, ${\displaystyle A_{5,3}=(16,19,93)}$, ${\displaystyle A_{5,4}=(82,75,68)}$, ${\displaystyle A_{5,5}=(24,54)}$.

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

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

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

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

• первоначально используемая Шеллом последовательность длин промежутков: ${\displaystyle ~d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1}$ в худшем случае, сложность алгоритма составит ${\displaystyle O(N^{2})}$;
• предложенная Хиббардом последовательность: все значения ${\displaystyle ~2^{i}-1\leq N,i\in \mathbb {N} }$; такая последовательность шагов приводит к алгоритму сложностью ${\displaystyle O(N^{3/2})}$;
• предложенная Седжвиком последовательность: ${\displaystyle ~d_{i}=9\cdot 2^{i}-9\cdot 2^{i/2}+1}$, если i четное и ${\displaystyle ~d_{i}=8\cdot 2^{i}-6\cdot 2^{(i+1)/2}+1}$, если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: ${\displaystyle O(n^{7/6})}$, а в худшем случае порядка ${\displaystyle O(n^{4/3})}$. При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.^[1];
• предложенная Праттом последовательность: все значения ${\displaystyle ~2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N} }$; в таком случае сложность алгоритма составляет ${\displaystyle O(N(logN)^{2})}$;
• эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ${\displaystyle ~d\in \left\{1,4,10,23,57,132,301,701,1750\right\}}$; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.^[2];
• эмпирическая последовательность, основанная на числах Фибоначчи: ${\displaystyle ~d\in \left\{F_{n}\right\}}$;
• все значения ${\displaystyle ~(3^{j}-1)\leq N}$ ^{[источник не указан 2742 дня]}, ${\displaystyle j\in \mathbb {N} }$; такая последовательность шагов приводит к алгоритму сложностью ${\displaystyle O(N^{3/2})}$.

Реализация на C++

template< typename RandomAccessIterator, typename Compare >
void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )
{
    for( typename std::iterator_traits< RandomAccessIterator >::difference_type d = ( last - first ) / 2; d != 0; d /= 2 )
        for( RandomAccessIterator i = first + d; i != last; ++i )
            for( RandomAccessIterator j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )
                std::swap( *j, *( j - d ) );
}

Реализация на C

// BaseType - любой перечисляемый тип 
// typedef int BaseType - пример
void ShellsSort(BaseType *A, unsigned N)
{
	unsigned i,j,k;
	BaseType t;
	for(k = N/2; k > 0; k /=2)
        for(i = k; i < N; i++)
        {
            t = A[i];
            for(j = i; j>=k; j-=k)
            {
                if(t < A[j-k])
                    A[j] = A[j-k];
                else
                    break;
            }
            A[j] = t;
        }
}

Примечания

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