Главная
Статьи





30.09.2022


30.09.2022


30.09.2022


30.09.2022


30.09.2022






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

20.06.2022

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

Описание

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

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

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

История

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

Пример


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

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

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

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

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

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

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

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

template< typename RandomAccessIterator, typename Compare > void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp ) { for( auto d = ( last - first ) / 2; d != 0; d /= 2 ) //нужен цикл для first = a[0..d-1] for( auto i = first + d; i != last; ++i ) for( auto j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d ) std::swap( *j, *( j - d ) ); }

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

void shell_sort(int *array, int size) { for (int s = size / 2; s > 0; s /= 2) { for (int i = s; i < size; ++i) { for (int j = i - s; j >= 0 && array[j] > array[j + s]; j -= s) { int temp = array[j]; array[j] = array[j + s]; array[j + s] = temp; } } } }

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

for (int step = n / 2; step > 0; step /= 2) { for (int i = step; i < n; i++) { for (int j = i - step; j >= 0 && a[j] > a[j + step] ; j -= step) { int x = a[j]; a[j] = a[j + step]; a[j + step] = x; } } }

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

def shell_sort(data: list[int]) -> list[int]: last_index = len(data) step = len(data)//2 while step > 0: for i in range(step, last_index, 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