Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
Описание
При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек;
- отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.
Выбор длины промежутков
Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:
- первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит ;
- предложенная Хиббардом последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью;
- предложенная Седжвиком последовательность: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: , а в худшем случае порядка . При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.;
- предложенная Праттом последовательность: все значения ; в таком случае сложность алгоритма составляет ;
- эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.;
- эмпирическая последовательность, основанная на числах Фибоначчи: ;
- все значения , ; такая последовательность шагов приводит к алгоритму сложностью .
Расчетный пример
Пусть дан список A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.
На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки
A5,1=(32,66,40),
A5,2=(95,35,43),
A5,3=(16,19,93),
A5,4=(82,75,68),
A5,5=(24,54).
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Реализация сортировки Шелла c шагом 3*k+1 на Pascal
type TElement = Integer;
{ сортировка Шелла с шагом 3*k+1 }
procedure ssort(var a: array of TElement);
var
gap, lt, rt, i: Integer;
t: TElement;
begin
gap:=1; while gap<=High(a) do gap:=3*gap+1; gap:=gap div 3;
while gap>0 do begin
for i:=0 to High(a)-gap do begin
lt:=i; rt:=lt+gap; t:=a[rt];
while (lt>=0) and (a[lt]>t) do begin
a[rt]:=a[lt]; rt:=lt; Dec(lt,gap);
end;
a[rt]:=t;
end;
gap:=gap div 3;
end;
end;
{ пример использования }
var
a: array [1..10] of TElement;
i: Integer;
begin
Randomize;
for i:=Low(a) to High(a) do a[i]:=-99+Random(199);
Write('A ='); for i:=Low(a) to High(a) do Write(a[i]:4); WriteLn;
ssort(a);
Write('A''='); for i:=Low(a) to High(a) do Write(a[i]:4); WriteLn;
end.
Реализация алгоритма сортировки н Python
def shell_sort(data: List[int]) -> List[int]:
last_index = len(data) - 1
step = len(data)//2
while step > 0:
for i in range(step, last_index + 1, 1):
j = i
delta = j - step
while delta >= 0 and data[delta] > data[j]:
data[delta], data[j] = data[j], data[delta]
j = delta
delta = j - step
step //= 2
return data