Вычислительная сложность рассматриваемых нами алгоритмов постепенно повышается. Вместе с этим усложняется их реализация и понимание. Значит, начинается что-то интересное! Сортировка Шелла (Shell sort) находится между простыми и сложными сортировками. И для этого есть причины, которые мы сегодня рассмотрим.
По своей сути сортировка Шелла является модификацией сортировки вставками, о которой мы рассказывали в предыдущей статье. Коротко напомним. При сортировке вставкой массив проходится слева направо. Берём элемент и ищем, куда его можно вставить в левой части массива так, чтобы слева находилось меньшее число, а справа — большее. И делаем так с каждым последующим элементом. Сложность алгоритма вставками в худшем случае равняется O(n2).
«Что, если мы будем идти не по всему массиву, а будем выполнять сортировку вставками в подмассивах, которые представляют собой элементы исходного массива, взятые с определённым интервалом?» — наверное, подумал Дональд Шелл и в 1959 году опубликовал эту идею.
Попробуем её продемонстрировать. Допустим, у нас есть массив элементов:
(а1, а2, а3, а4, а5, а6, а7, а8, а9, а10, а11)
Применим алгоритм сортировки вставками к подмассиву, состоящему из каждого 5-го элемента, выглядеть он будет так:
(а1, а6, а11)
Сохраняем результат сортировки в основном массиве. И теперь, с тем же интервалом между элементами, сдвигаемся на элемент вправо и сортируем подмассив (а2, а7), затем то же самое для (а3, а8). И делаем так, пока не дойдём до конца массива.
Далее, возьмём подмассив из каждого 3-го элемента:
(а1, а4, а7, а10)
Опять сохраняем результат сортировки в основном массиве. Затем, уже привычным движением сдвигаемся на один элемент вправо, получаем подмассив:
(а2, а5, а8, а11)
Сортируем так и далее.
В конце, выполняем обычную сортировку вставками для всего массива, который уже является частично отсортированным. Вот и вся идея.
А теперь самое интересное: сложность алгоритма будет зависеть от того, какие интервалы выбрать между элементами для выделения подмассивов. Вариантов много, перечислим самые популярные:
Последовательность Шелла
Первый интервал между элементами равен длине массива. На каждом следующем шаге интервал уменьшается вдвое. Вычислительная сложность в худшем случае — O(n2).
Последовательность Хиббарда
Берутся конкретные расстояния между элементами, вычисляемые по формуле 2k-1. В худшем случае получаем O(n1.5).
Последовательность Седжвика
Формула сложная и здесь не поместится. Вычислительная сложность в худшем случае — O(n4/3).
Последовательность Пратта
Все произведения степеней двойки и тройки. Вычислительная сложность в худшем случае — O(n log2n).
Последовательность Циура
Считается лучшим предложенным рядом. Получена экспериментально, и данных о вычислительной сложности нет. Полагаем, она должна быть близка к O(n log n).
Вот почему мы не можем отнести этот алгоритм ни к простым, ни к сложным. Его вычислительная сложность сильно зависит от размера массива и от выбранной последовательности. А выбрать или рассчитать последовательность саму — дело не самое простое!
Узнать больше о других видах сортировок вы можете из материалов блога: