Сортировка Шелла () — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
Описание При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
отсутствие потребности в памяти под стек; отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до , что хуже, чем худшее гарантированное время для сортировки Шелла.
История Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.
Пример
Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .
На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Выбор длины промежутков Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:
первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит ; предложенная Хиббардом последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью ; предложенная Седжвиком последовательность: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: , а в худшем случае порядка . При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.; предложенная Праттом последовательность: все значения ; в таком случае сложность алгоритма составляет ; эмпирическая последовательность Марцина Циура (): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.; эмпирическая последовательность, основанная на числах Фибоначчи: .
Реализация на языках программирования
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 ) 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 ) ); }
Си void check_and_swap(int i, int shift, int* nums) { for (int j = i - shift; j >= 0; j -= shift) if (nums[j] > nums[j + shift]) { int temp = nums[j]; nums[j] = nums[j + shift]; nums[j + shift] = temp;
void shell_sort(int *array, int size) { for (int s = size / 2; s > 0; s /= 2)
if (s > 1) for (int s_add = 0; s_add < s - 1; s_add++) for (int i = s + s_add; i < size; ++i) check_and_swap(i, s, array); else for (int i = s; i < size; ++i) check_and_swap(i, s, array);
Java void shell_sort(List<Integer> array) { for (int s = array.size() / 2; s > 0; s /= 2) for (int i = s; i < array.size(); ++i) for (int j = i - s; j >= 0 && array.get(j) > array.get(j + s); j -= s) Collections.swap(array, j, j + s); }
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
Примечания
Ссылки
Дональд Кнут. Искусство программирования. Том 3. Сортировка и поиск, 2-е изд. Гл. 5.2.1. ISBN 5-8459-0082-4 Анимированное представление алгоритма сортировки Шелла Представление алгоритма сортировки Шелла в виде танца (видео)
Категория:Алгоритмы сортировки