- Сортировка Шелла
-
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
Содержание
Описание
При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии
(о выборе значения
см. ниже). После этого процедура повторяется для некоторых меньших значений
, а завершается сортировка Шелла упорядочиванием элементов при
(то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек;
- отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.
История
Сортировка Шелла была названа в честь её изобретателя — Да Шелла, который опубликовал этот алгоритм в 1959 году.
Пример
Пусть дан списоки выполняется его сортировка методом Шелла, а в качестве значений
выбраны
.
На первом шаге сортируются подсписки
, составленные из всех элементов
, различающихся на 5 позиций, то есть подсписки
,
,
,
,
.
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Выбор длины промежутков
Среднее время работы алгоритма зависит от длин промежутков —
, на которых будут находиться сортируемые элементы исходного массива ёмкостью
на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:
- первоначально используемая Шеллом последовательность длин промежутков:
в худшем случае, сложность алгоритма составит
;
- предложенная Хиббардом последовательность: все значения
; такая последовательность шагов приводит к алгоритму сложностью
;
- предложенная Седжвиком последовательность:
, если i четное и
, если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет:
, а в худшем случае порядка
. При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.[1];
- предложенная Праттом последовательность: все значения
; в таком случае сложность алгоритма составляет
;
- эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS):
; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.[2];
- эмпирическая последовательность, основанная на числах Фибоначчи:
;
- все значения
,
; такая последовательность шагов приводит к алгоритму сложностью
.
Примечания
- ↑ J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
- ↑ Marcin Ciura Best Increments for the Average Case of Shellsort
Ссылки
- Д. Кнут. Искусство программирования. Том 3. Сортировка и поиск, 2-е изд. Гл. 5.2.1. ISBN 5-8459-0082-4
- Анимированное представление алгоритма сортировки Шелла
- Представление алгоритма сортировки Шелла в виде танца (видео)
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.