Глава 1     Глава 2   

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



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

Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии 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



- Начало - - Назад - - Вперед -



Книжный магазин