Сортировка включениями с убывающими приращениями (сортировка Шелла).

На 1-м проходе группируются и сортируются все эл-ты стоящие друг от друга на 4 позиции. Этот процесс называется четыре сортировкой. После этого эл-ты вновь определяются в группы с эл-ми стоящими друг от друга на две позиции и сортируются заново – это двухсортировка. Наконец все эл-ты сортируются обычной сортировкой (одинсортировкой).

Может показаться, что необходимость нескольких проходов сортировки в которых участвуют все эл-ты потребуют больше места, чем сэкономит. Однако на каждый шаг сортировки либо участвуют сравнительно мало эл-тов, либо они уже довольно хорошо упорядочены и требуют относительно малых перестановок. Применима любая последовательность приращений, либо последняя равна 1, т. к в худшем случае вся работа будет выполнятся на последнем проходе. Программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращения обозначаются h1,h2,…,ht

ht:=1, hi+1<hi

Каждая h сортировка программируется как сортировка простыми включениями. При этом

чтобы условия окончания поиска метода включения было простым, используется вместо барьера …. Очевидно, что каждая h сортировка требует собственного барьера и программа должна определять его как можно проще, поэтому массив нужно дополнять не одной компонентой а0, а h1 компонентами. Теперь массив описывается таким образом

а:array [-h1..n] of item

const t=4; var I,j,k,s:index; x:item; m:1..t; h:array [1..t] of integer; begin h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=1; for m:=1 to t do

begin k:=h[m]; s:=-k; {место барьера} for i:=k+1 to n do begin x:=a[i]; j:=i-k; if s=0 then s:=-k; s:=s+1; a[s]:=x{определили барьер} while x<a[j] do begin a[j+k]:=a[j]; j:=j-k; end; end; a[j+k]:=x; end; end;

Не нашли, что искали? Воспользуйтесь поиском: