Сортировка Шелла (Нюркин, ИСТ-21)

1.

Сортировка Шелла
Дональд Шелл — американский учёный в области
информатики, который разработал алгоритм сортировки
массива — метод Шелла.
Сортировка Шелла является одной из наиболее интересных и
эффективных алгоритмических техник для упорядочивания
массивов и коллекций в языке программирования C#. Этот
метод сортировки является усовершенствованной версией
простой сортировки вставками, обладая при этом лучшей
производительностью за счёт использования прыжков между
элементами во время их сравнения и перемещения.
Дональд Шелл
Подготовил: Нюркин Илья, ИСТ-11
Димитровградский инженерно-технологический институт – филиал федерального государственного автономного
образовательного учреждения высшего образования «Национальный исследовательский ядерный университет «МИФИ»

2.

Понимание алгоритма сортировки Шелла
- Сортировка Шелла, разработанная Дональдом Шеллом в 1959 году, представляет собой алгоритм, который
упорядочивает элементы в массиве, сравнивая их не только с соседними элементами, как в сортировке вставками, но и
с элементами, стоящими на определённом расстоянии друг от друга. Это расстояние называется интервалом, и оно
уменьшается с каждым проходом алгоритма;
- выбор интервала является критически важным для производительности сортировки Шелла. Исходный интервал
часто определяется как половина длины массива, но существуют различные стратегии его уменьшения. Одна из
популярных стратегий — последовательность Марцина Циура, где интервалы предварительно рассчитаны и
обеспечивают хорошую производительность;
- оптимизация сортировки Шелла может заключаться в выборе более эффективной последовательности
уменьшения интервала. Кроме того, могут быть применены различные эвристические методы для минимизации
количества сравнений и перемещений элементов, такие как предварительный расчёт интервалов или динамическое их
определение во время выполнения алгоритма.

3.

Сложность алгоритма сортировки Шелла
Точная оценка временной сложности сортировки Шелла неизвестна, так как она зависит от выбранной последовательности
интервалов. Однако в общем случае она лежит между O(n) и O(n^2), что делает её быстрее, чем традиционная сортировка вставками, и
в некоторых случаях — близкой к более сложным алгоритмам сортировки, таким как быстрая сортировка.
Время
Временная сложность алгоритма
Худшее время
O(n^2)
Лучшее время
O(n*log^2 n)
Среднее время
Зависит от выбранных шагов
Затраты памяти
O(n) всего, O(1) дополнительно

4.

Преимущества и недостатки сортировки Шелла
Преимущества
Недостатки
проста в понимании и реализации;
адаптивна (может улучшать производительность за
счёт использования различных
последовательностей интервалов);
алгоритм не является устойчивым (может изменять
порядок равных элементов);
эффективна для средних и относительно малых
данных.
алгоритм имеет более высокую сложность по
сравнению с более продвинутыми алгоритмами для
больших объёмов данных.

5.

Принцип работы сортировки Шелла
Принцип работы сортировки Шелла заключается в
следующем: сначала выбирается начальный интервал, часто
равный половине длины массива. На каждом шаге элементы,
находящиеся на расстоянии интервала друг от друга,
сравниваются и, если нужно, меняются местами. После
завершения первого прохода интервал уменьшается,
например, вдвое, и процесс повторяется, пока интервал не
станет равен 1. На последнем этапе сортировка Шелла
сводится к обычной сортировке вставками.
Например, пусть дан список 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 позиции элементов.
Процесс завершается обычной сортировкой вставками
получившегося списка.
пример

6.

Реализация сортировки Шелла в C#
public static void ShellSort(int[] array)
{
int n = array.Length;
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int temp = array[i];
int j;
for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
{
array[j] = array[j - gap];
}
array[j] = temp;
}
gap /= 2;
}
}

7.

Реализация сортировки Шелла на Python
результат
код программы

8.

Особенность сортировки Шелла как списка в Python
Сортировка Шелла — это улучшенный вариант сортировки вставками, который работает быстрее на больших
списках за счёт использования промежуточных шагов (шагов разбиения или "gap"). Основная особенность
сортировки Шелла:
- Вместо сравнения и сортировки соседних элементов, она сравнивает элементы, отстоящие друг от друга на
некотором расстоянии (gap), постепенно уменьшая этот промежуток.
- Такой подход позволяет быстрее смещать элементы с большими индексами по списку, уменьшая общее количество
операций сдвига.
- На последнем шаге, когда gap равен 1, происходит обычная сортировка вставками, но уже по практически
упорядоченному массиву, что даёт быстрый результат.

9.

Конкретно в Python
- В стандартной библиотеке Python сортировка списков не реализована через сортировку Шелла, а использует
алгоритм Timsort — гибрид сортировки слиянием и вставками.
- Однако пользователь может реализовать сортировку Шелла самостоятельно для обучения или специфических
задач.
- Реализация сортировки Шелла в Python позволяет гибко управлять шагом разбиения и часто демонстрирует
хороший компромисс между простотой кода и эффективностью для средних и небольших наборов данных.

10.

Заключение
В заключение, сортировка Шелла представляет собой мощный и гибкий алгоритм, который может быть
оптимизирован для различных условий и типов данных. Понимание её принципов и особенностей
реализации позволит эффективно использовать данный метод для упорядочивания данных в
программных проектах.
Сортировка Шелла отличается тем, что она постепенно уменьшает расстояние между сравниваемыми
элементами, что уменьшает количество перемещений элементов и ускоряет сортировку по сравнению с
классической сортировкой вставками. В Python данный алгоритм не является встроенным, но может
быть реализован вручную.
СПАСИБО ЗА ВНИМАНИЕ.