ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6813
Скачиваний: 51
281
begin write (a[i], ' ');
end;
writeln;
(*алгоритм сортировки двоичным включением*)
for i:=2 to n do begin
x:=a(i]; L:=l; R:=i;
while L<R do begin
m:=(L+R) div 2; if a[m]<=x then L:=m+l else R:=m;
end;
for j:=i downto R+l do a(j]
:=a
[j-1];
a[R]:-x;
end;
(* вывод отсортированного массива*)
for i:=l to N do
begin write(a[i], ' ');
end; , readln;
end.
Один
из вариантов
улучшенной сортировки включением
был предложен Д.Шеллом. Его
метод предполагает сначала отдельную группировку и сортировку элементов, отстоящих друг от
друга на некотором расстоянии, например 4 (четвертная сортировка), после первого прохода пере-
группировку элементов таким образом, чтобы каждый элемент группы отстоял от другого на 2
номера, после двойной сортировки на третьем проходе одинарную (обычную) сортировку.
Каждая из сортировок основывается на алгоритме прямого включения и, соответственно,
должна программироваться аналогично. Если для условия окончания поиска использовать барьер,
а их необходимо ставить для каждой из сортировок, то необходимо расширить границы массива
на несколько компонентов (барьеров) влево, т.е. использовать массив а[-r..n], где r - количество
сортировок.
Сортировка с помощью прямого выбора
.
Алгоритм прямого выбора является одним из
распространенных в силу своей простоты. Сначала определяют минимальный элемент среди всех
элементов массива, затем его меняют местами с первым. Далее процесс повторяется с той лишь
разницей, что минимальный ищется со второго и меняется со вторым и т.д.
1
2
3
4
5
12
15
17
11
13
i=2, min= 11
11
15
17
12
13
i=3.min=12
11
12
17
15
13
i=4, min=13
11
12
13
15
17
i=5,min=15.
Программа 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;
Исходные элементы
44
5
5
1
2
4
2
9
4
1
8
6
6
7
Четвертная сортировка
44
1
8
6
4
2
9
4
5
5
1
2
6
7
Двойная сортировка
6
1
8
1
2
4
2
4
4
5
5
9
4
6
7
Одинарная сортировка
6
1
2
1
8
4
2
4
4
5
5
6
7
9
4
282
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.
Улучшенный метод сортировки выбором с помощью дерева
.
Метод сортировки прямым
выбором основан на поисках наименьшего элемента среди неготовой последовательности. Уси-
283
лить метод можно запоминанием информации при сравнении пар элементов. Этого добиваются
определением в каждой паре меньшего элемента за n/2 сравнений. Далее n/4 сравнений позволит
выбрать меньший из пары уже выбранных меньших и т.д. Получается двоичное дерево сравнений
после n-1 сравнений у которого в корневой вершине находится наименьший элемент, а любая
вершина содержит меньший элемент из двух приходящих к ней вершин. Одним из алгоритмов,
использующих структуру дерева, является сортировка с помощью пирамиды (Дж.Вилльямс). Пи-
рамида определяется как последовательность ключей hL...hR, такая, что *
hi<=h2i и hi<=h2i+l, для i=L,...,R/2.
Другими словами пирамиду можно определить как двоичное дерево заданной высоты h,
обладающее тремя свойствами:
• каждая конечная вершина имеет высоту h или h-1;
• каждая конечная вершина высоты h находится слева от любой конечной вершины высоты
h-1;
• значение любой вершины больше значения любой следующей за ней вершины. Рассмот-
рим пример пирамиды, составленной по массиву
27 9 14 8 5 11 7 2 3.
У пирамиды п вершин, их значения можно разместить в массиве а, но таким образом, что
следующие за вершиной из a[i] помещаются в a[2i] и a[2i+l]. Заметим, что а[6]=11,а[7]=7, а они
следуют за элементом а[3]=14 (рис.3.14).
Рис. 3.14. Пирамида
Очевидно, что если 2i > n , тогда за вершиной a[i] не следуют другие вершины, и она явля-
ется конечной вершиной пирамиды.
Процесс построения пирамиды для заданного массива можно разбить на четыре этапа:
1) меняя местами а[1] и а[п], получаем 3 9 14 8 5 11 7 2 27;
2) уменьшаем n на 1, т. е. n=n-l, что эквивалентно удалению вершины 27 из дерева;
3) преобразуем дерево в другую пирамиду перестановкой нового корня с большей из двух
новых, непосредственно следующих за ним вершин, до тек пор, пока он не станет больше, чем обе
вершины, непосредственно за ним следующие;
4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n= I.
Для алгоритма сортировки нужна процедура преобразования произвольного массива в пи-
рамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа на-
лево с проверкой одновременно двух условий: больше ли a[i], чем a[2i] и a[2i+l].
Полный текст программы приведен
ниже.
Программа 48
program sortirovka_5;
(*улучшенная сортировка выбором - сортировка с помощью дерева*) const
N=8;
type item= integer;
var a : array(l..n] of item; k, L, R: integer; x: item;
procedure sift(L,R:integer);
var i, j: integer; x,y: item;
begin i:=L; j:=2*L; x:=a[L]; if (j<R) and (a[j]<a[j+1]) then j:=j+l;
while (j<=R)and(x<a[j]) do begin y:=a[i]; a[i]:=a[j];
а[j]:=y a[i]:=a[j]; i:=j; j:=2*j;
if (j<R)and(a[j]<a(j+l]) thenj:=j+l;
end;
end;
284
begin
(*задание искомого массива*) for k:=l to N do begin
write('введи элемент a[',k,']=');
readln(a[k]) ;
end;
for k:=l to N do begin write(a[k], ' ');
end;
writeln;
(*алгоритм сортировки с помощью дерева*) (*построение пирамиды*)
L:=(n div 2) +1; R:=n; while L>1 do begin L:=L-1; SIFT(L,R);
end;
(*сортировка*) while R>1 do begin x:=a[l]; a[l]:=a[R];
a(R]:=x;
R:=R-1; SIET(1,R);
end;
(*вывод отсортированного массива*) for k:=l to N do
begin write(a[k],' ');
end;
readin;
end.
Сортировка с помощью обменов.
Характерной чертой алгоритмов сортировки с помощью
обмена является обмен местами двух элементов массива после их сравнения друг с другом. В так
называемой «пузырьковой сортировке» проводят несколько проходов по массиву, в каждом из ко-
торых повторяется одна и та же процедура: сравнение двух последовательно стоящих элементов и
их обмен местами в порядке меньшинства (старшинства) Подобная процедура сдвигает наимень-
шие элементы к левому концу массива. Название этого алгоритма связано с интерпретацией эле-
ментов как пузырей в сосуде с водой, обладающих весом соответствующего элемента (при этом
массив надо представлять в вертикальном положении). При каждом проходе пузырьки всплывают
до своего уровня.
Программа 49
program 5ortirovka_6;
(*сортировка прямым обменом - пузырьковая сортировка*)
const N=5;
type item= integer; var a: array(l,.n] of item; i, j: integer;
x: item;
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;
(*алгоритм пузырьковой сортировки*) for i:=2 to n do for j:=n downto i do
begin
if a[j-l]>a[j] then begin x:=a [j-1] ;a [j-1] :=a[j]; a[j]:=x;
1
end;
end;
(*вывод отсортированного массива*) for i:=l to N do
begin write(a[i], ' ');
end;
readln;
end.
Представленную программу можно легко улучшить, если учесть, что если после очередно-
го прохода перестановок не было, то последовательность элементов уже упорядочена, т.е. про-
должать проходы не имеет смысла. Читатель без труда сможет внести коррективы в программу,
использовав логическую переменную, которая контролировала бы факт обмена.
285
Если чередовать направление последовательных просмотров, алгоритм улучшается. Такой
алгоритм называют «шейкерной» сортировкой.
Программа 50
program sortirovka_7;
(*сортировка прямым обменом - шейкерная сортировка*) const N=5;
type item= integer;
var a: array[l..n] of item; i, j, k, L, R: integer; x: item;
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;
(*алгоритм шейкерной сортировки*) L:=2; R:=n; k:=n;
repeat
for j:=R downto L do begin
if a[j-l]>a[j] then begin x:=a[j-l];a[j-l]:=a[j];
a(j]:
=
x; k:=j
end;
end;
L:=k+l;
for j:=L to R do begin
if a[j-l]>a[j] then begin x:=a(j-l];
a[j-l]:=a[j]; a[j]:=x; k:=j end;
end;
R:=k-l;
until L>R;
(*вывод отсортированного массива*)
for i:=l to N do
begin write(a[i],' ');
end; readln;
end.
Пузырьковая сортировка является не самой эффективной, особенно для последовательно-
стей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной
(быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстоя-
ния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из ко-
торых один берется слева (i = 1), другой -справа (j = n). Если a[i] <= a[j] , то устанавливают j = j - 1
и проводят следующее сравнение. Далее уменьшают j до тех пор, пока a[i] > a[j]. В противном
случае меняем их местами и устанавливаем i = i + 1. Увеличение i продолжаем до тех пор, пока не
получим a[i] > a[j]. После следующего обмена опять уменьшаем j. Чередуя уменьшение j и увели-
чение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i= j. После этого этапа
возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него
младшие элементы, а справа - старшие.
Далее подобную процедуру можно применить к левой и правой частям массива и т.д. Оче-
видно, что характер алгоритма рекурсивный. Для запоминания ведущих левого и правого элемен-
тов в программе необходимо использовать
стек.
Программа 51
program sortirovka_8;
(*улучшенная сортировка разделением - быстрая сортировка с рекур-
сией*) const N=8;
type item= integer;
var a: array(l..n] of item; i: integer;
procedure sort(L,R: integer);
var i, j :• integer; x, y: item;
begin
i:=L; j:=R; x:=a[(L+R) div 2];