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

В методе Шелла сравниваются не соседние элементы, а элементы, расположенные на расстоянии d (где d – шаг между сравниваемыми элементами) d = [n/2]. После каждого просмотра шаг d уменьшается вдвое. На последнем просмотре он сокращается до d = 1.

Например, пусть дан список, в котором число элементов чётно:

{40, 11, 83, 57, 32, 21, 75, 64}

Список длины n разбивается на n/2 частей, т.е. d = [n/2] = 4.

Исходный массив	40	11	83	57	32	21	75	64
d = 4	32	11	75	57	40	21	83	64
Полученный массив	32	11	75	57	40	21	83	64

Рис. 5. Метод Шелла (d=4 )

Исходный массив	32	11	75	57	40	21	83	64
d = 2	32	11	75 40	57 21	75 75	57 57	83	64
Полученный массив	32	11	40	21	75	57	83	64

Рис. 6. Метод Шелла (d=2 )

При первом просмотре сравниваются элементы, отстоящие друг от друга на d = 4 (рис.5), т.е. k₁ и k₅, k₂ и k₆ и т.д. Если k_i > k_i+d, то происходит обмен между позициями i и (i+d). Перед вторым просмотром выбирается шаг d = [d / 2] = 2 ( рис.6 ). Затем выбираем шаг d = [d / 2] = 1 ( рис.7 ), т.е. имеем аналогию с методом стандартного обмена.

Сложность метода Шелла O(0,3n(log₂n)²).

Исходный список	32	11	40	21	75	57	83	64
d =1	11	32 32	40 21	40 40	75 57	75 75	83 64	83
Полученный список	11	32	21	40	57	75	64

Рис. 7. Метод Шелла (d=1 )