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

Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при d=1. Качественный порядок сортировки Шелла остается O(N^2), среднее же число сравнений, определенное эмпирическим путем - log2(N)^2*N. Ускорение достигается за счет того, что выяв- ленные "не на месте" элементы при d>1, быстрее "всплывают" на свои места.

Пример 3.10 иллюстрирует сортировку Шелла.

{===== Программный пример 3.10 =====}

Procedure Sort(var a: seq);

Var d, i, t: integer; k: boolean; { признак перестановки }

begin d:=N div 2; { начальное значение интервала }

while d > 0 do { цикл с уменьшением интервала до 1 }

begin k:=true; {пузырьковая сортировка с интервалом d}

while k do { цикл, пока есть перестановки }

begin k:=false; i:=1;

for i:=1 to N-d do { сравнение эл-тов на интервале d }

begin if a[i] > a[i+d] then begin

t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; { перестановка }

k:=true; { признак перестановки }

end; { if... } end; { for... } end; { while k }

d:=d div 2; { уменьшение интервала }

end; { while d>0 } end;

Результаты трассировки программного примера 3.10 представлены в таблице 3.7.

Шаг	d	Содержимое массива а
Исходный		76 22_ 4 17 13 49_ 4 18 32 40 96 57 77 20_ 1 52
		32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
		32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
		_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
		_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
		_1_ 4 17_ 4 18 13 20 22 32 40 49 76 52 77 57 96
		_1_ 4_ 4 17 13 18 20 22 32 40 49 52 76 57 77 96
		_1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96
		_1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96
Результат		_1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96

Таблица 3.7