3. Алгоритм Шелла (ShellSort)

Идея этого алгоритма в следующем. Разобьем элементы сортируемого массива на hцепочек, каждая из которых состоит из элементов, отстоящих друг от друга на расстояниеh(здесьh– произвольное натуральное число). Первая цепочка будет содержать элементыa₁,a_h+1,a_2h+1,a_3h+1и т.д., вторая –a₂,a_h+2,a_2h+2и т.д., последняя цепочка –a_h,a_2h,a_3hи т.д. Отсортируем каждую цепочку как отдельный массив, используя для этого метод простых или бинарных вставок. Затем выполним все вышеописанное для ряда убывающих значенийh, причем последний раз – дляh = 1.

Очевидно, массив после этого окажется сортированным. Неочевидно, что все проходы при h > 1не были пустой тратой времени. Тем не менее, оказывается, что дальние переносы элементов при большихhнастолько приближают массив к сортированному состоянию, что на последний проход остается очень мало работы.

Большое значение для эффективности алгоритма Шелла имеет удачный выбор убывающей последовательности значений h. Казалось бы, самая естественная убывающая последовательность чисел это степени двойки: …, 64, 32, 16, 8, 4, 2, 1. Сам автор алгоритма Дональд Шелл первоначально предложил использовать именно эти числа. На самом же деле выбор этой последовательности – один из самых неудачных! Пусть, например, в исходном массиве все нечетные по номеру элементы отрицательны, а четные – положительны. Как будет выглядеть такой массив после выполнения всех проходов, кроме последнего (сh= 1)? Поскольку все использованныеhбыли четными, ни один элемент не мог переместиться с четного места на нечетное и наоборот. Таким образом, все нечетные элементы по-прежнему будут отрицательны (хотя и отсортированы между собой), а четные – положительны. Подобный массив трудно назвать «почти сортированным»! На последний проход алгоритма вставки остается слишком много работы.

Чтобы избежать подобной неприятности, желательно, чтобы при соседних значениях kзначенияh_kне были кратны друг другу. В литературе обычно рекомендуется использовать одну из двух последовательностей:h_k+1=3h_k+1илиh_k+1=2h_k+1. В обоих случаях в качестве начальногоh_kвыбирается такое значение из последовательности, при котором все сортируемые цепочки имеют длину не меньше 2. Чтобы воспользоваться, например, первой из этих формул, надо сначала положитьh₁:=1, а затем в цикле увеличивать значениеhпо формулеh_k+1 := 3*h_k+1, пока для очередногоh_kне будет выполнено неравенствоh_k    (n–1) div 3. Это значениеh_kследует использовать на первом проходе алгоритма, а затем можно получать следующие значения по обратной формуле:h_k–1 := (h_k–1) div 3, вплоть доh₁=1.

Для каждой из этих двух последовательностей время работы в худшем случае оценивается как T_макс(n) = O(n^3/2). Это значительно лучше, чемO(n²)для простых алгоритмов. Для среднего времени работы известны только эмпирические оценки, показывающие, что время растет примерно какO(n^1.25)илиO(n^1.3).

Ряд авторов на основе теоретического анализа сортировки Шелла предложили использовать более сложные последовательности, повышающие эффективность алгоритма. Одной из лучших считается последовательность, предложенная Р.Седжвиком:

Доказано, что при выборе h_kпо Седжвику максимальное время работы алгоритма естьO(n^4/3). Среднее время по эмпирическим оценкам равно примерноO(n^7/6).

На практике удобно раз и навсегда вычислить достаточное количество членов последовательности Седжвика (вот они: 1, 5, 19, 41, 109, 209, 505, 929, 2 161, 3 905, 8 929, 16 001, 36 289, 64 769, 14 6305, 260 609, 587 521, 1 045 505, ...), затем по заданномуnвыбрать такоеk, при которомh_k >= (n–1) div 3, а далее в цикле выбирать значения последовательностиh_kпо убываниюk.