Сортировка Шелла (ShellSort)

Сортировка Шелла (ShellSort) — это алгоритм сортировки, который является обобщением сортировки вставками. Он был предложен Дональдом Шеллом в 1959 году. Основная идея алгоритма заключается в том, чтобы сначала сортировать элементы, которые находятся на определённом расстоянии друг от друга, а затем постепенно уменьшать это расстояние до 1, когда выполняется обычная сортировка вставками.

▎Принцип работы

1. Шаги и промежуточные последовательности: Алгоритм начинает с выбора начального значения "шага" (или "разрыва"), которое определяет, как далеко друг от друга будут сравниваться элементы. Обычно это значение уменьшается в процессе сортировки.

2. Сортировка по подмассивам: На каждом шаге алгоритм разбивает массив на подмассивы, состоящие из элементов, находящихся на расстоянии "шага" друг от друга. Например, если шаг равен 3, то будут сортироваться элементы с индексами 0, 3, 6 и т. д., затем элементы с индексами 1, 4, 7 и так далее.

3. Сортировка вставками: Для каждого подмассива выполняется сортировка вставками. Это позволяет расположить элементы в нужном порядке.

4. Уменьшение шага: После завершения сортировки для текущего шага значение шага уменьшается (обычно делится на 2 или уменьшается по другой заранее определённой последовательности).

5. Завершение: Процесс повторяется до тех пор, пока шаг не станет равным 1. В этот момент выполняется последняя сортировка вставками, которая окончательно упорядочивает массив.

▎Временная сложность

• Лучший случай: O(n*log^2(n))

• Средний случай: O(n^(3/2)) или O(n*log^2(n)) (в зависимости от выбора последовательности шагов)

• Худший случай: O(n^2) (для некоторых последовательностей шагов)

▎Пространственная сложность

O(1) - алгоритм сортирует массив "на месте".

▎Устойчивость:

Данный алгоритм сортировки не является устойчивым, это означает, что при сортировке элементов с одинаковыми ключами их относительный порядок не сохраняется. То есть, если два элемента имеют одинаковое значение и один из них идет перед другим в исходном массиве, то после сортировки первый элемент не обязательно останется перед вторым.

▎Особености:

• Простота реализации.

• Эффективен для небольших массивов.

• Работает лучше, чем простые алгоритмы сортировки (такие как пузырьковая или сортировка вставками) на больших массивах.

Реализация алгоритма на C++:

Реализация алгоритма на Python: