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

Толкование Перевод

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

Содержание

1 Описание

2 История

3 Пример

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

5 Примечания

6 Ссылки

Описание

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

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

отсутствие потребности в памяти под стек;

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

История

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

Пример

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

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

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

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

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

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

первоначально используемая Шеллом последовательность длин промежутков: $~d_1 = N/2, d_i = d_{i-1} / 2, d_k = 1$ в худшем случае, сложность алгоритма составит $O( N^2 )$ ;

предложенная Хиббардом последовательность: все значения $~2^i-1 \le N, i \in \mathbb N$ ; такая последовательность шагов приводит к алгоритму сложностью $O(N^{3/2})$ ;

предложенная Седжвиком последовательность: $~d_i = 9\cdot2^i - 9\cdot2^{i/2} + 1$ , если i четное и $~d_i = 8\cdot2^i - 6\cdot2^{(i+1)/2} + 1$ , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: $O(n^{7/6})$ , а в худшем случае порядка $O(n^{4/3})$ . При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.^[1];

предложенная Праттом последовательность: все значения $~2^i\cdot3^j \le N/2, i, j \in \mathbb N$ ; в таком случае сложность алгоритма составляет $O(N (log N)^2)$ ;

эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): $~d \in \left\{1, 4, 10, 23, 57, 132, 301, 701, 1750\right\}$ ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.^[2];

эмпирическая последовательность, основанная на числах Фибоначчи: $~d \in \left\{F_n\right\}$ ;

все значения $~(3^j-1)/2 \le N/2$ ^{[источник не указан 1119 дней]}, $j \in \mathbb N$ ; такая последовательность шагов приводит к алгоритму сложностью $O(N^{3/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 • Глупая • Блинная

Категория:
Алгоритмы сортировки

Игры ⚽ Поможем написать реферат

Полезное

Смотреть что такое "Сортировка Шелла" в других словарях:

Сортировка расчёской — (англ. comb sort) это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine … Википедия
Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п … Википедия
Сортировка выбором — (Selection sort) алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… … Википедия
Сортировка вставками — Сортировка вставками простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до … Википедия
Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… … Википедия
Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… … Википедия
Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… … Википедия
Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. … Википедия
Пирамидальная сортировка — Анимированная схема алгоритма Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) … Википедия
Сортировка методом Шелла — … Википедия

Пометить текст и поделиться
Искать во всех словарях
Искать в переводах
Искать в Интернете

Поделиться ссылкой на выделенное