Сортировка шелла.

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

Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии 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
1	8	32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
2	8	32 22_ 4 17 13 20_ 1 18 76 40 96 57 77 49_ 4 52
3	4	13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
4	4	13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
5	2	13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
6	2	13 20_ 1 17 32 22_ 4 18 76 40_ 4 52 77 49 96 57
7	2	_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
8	2	_1 17_ 4 18_ 4 20 13 22 32 40 76 49 77 52 96 57
9	1	_1_ 4 17_ 4 18 13 20 22 32 40 49 76 52 77 57 96
10	1	_1_ 4_ 4 17 13 18 20 22 32 40 49 52 76 57 77 96
11	1	_1_ 4_ 4 13 17 18 20 22 32 40 49 52 57 76 77 96
12	1	_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