Информатика -продвинутый курс
of item; i, j, k,
/p> Программа 46
program sortirovka_3;
(*улучшенная сортировка включением - сортировка Шелла*)
const N=8; t=4;
type item= integer;
var a: array[-9..n] of item; i, j, k, s :integer; x: item;
m: l..t; h :array [l..t] of integer;
begin
(*задание искомого массива*)
for i:=l to N do
begin write('введи элемент a[',i,']=')
readln(a[i])
end;
for i:=l to N do begin write(a[i], ' ');
end;
writeln;
(*алгоритм Шелла*)
h[l]:=9; h[2]:=5; h[3]:=3; h[4]:=1;
for m:=l to t do
begin k:=h[m]; s:=-k; (*барьеры для каждого шага*)
for i:=k+l to n do
begin x:=a[i], j:=i—k; if s=0 then s:=-k;- s:=s+l;
a[s]:=x; while x<a[j] do begin a[j+k]:=a(j]; j:=j-k;
end;
a[j+k]:=x
end;
end;
(*вывод отсортированного массива*)
for i:=l to N do begin write(a[i], ' ');
end;
readln;
end.
Программа 47
program sortirovka 4;
(*сортировка прямым выбором*)
const N=5;
type item= integer;
var a: array[l..n] of item; i, j, k: integer; x: item;
begin
(*задание искомого массива*)
for i: =1 to N do
begin write('введи элемент a[', i, ']='); readln(a[i]);
end;
for i:=l to N do begin write(a[i],' ');
end;
writeln;
(*алгоритм прямого выбора*)
for i:=l to n-1 do
begin k:=i; x:=a[i]; (*поиск наименьшего элемента*)
for j:=i+l to n do (*и его индекса из a[i]...a{n]*)
if a[j]<x then begin k:=j; x:=a[k)
end;
a(k]:=a[i]; a[i]:=x;
end;
(*вывод отсортированного массива*)
for i:=l to N do begin write(a[i], ' ');
end;
readln;
end.
Улучшенный метод сортировки выбором с помощью дерева. Метод сортировки прямым выбором основан на поисках наименьшего элемента среди неготовой последовательности. Усилить метод можно запоминанием информации при сравнении пар элементов. Этого добиваются определением в каждой паре меньшего элемента за n/2 сравнений. Далее n/4 сравнений позволит выбрать меньший из пары уже выбранных меньших и т.д. Получается двоичное дерево сравнений после n-1 сравнений у которого в корневой вершине находится наименьший элемент, а любая вершина содержит меньший элемент из двух приходящих к ней вершин.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий