Сортировка Шелла — Pascal(Паскаль) Python(Питон)

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

Описание

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

Работа алгоритма Шелла

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

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

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

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

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

Расчетный пример

Пусть дан список 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

Leave a Comment

1 + 9 =