Основы дискретной математики

• значение любой вершины больше значения любой следующей за ней вершины.

Рассмотрим пример пирамиды, составленной по массиву 27 9 14 8 5 11 7 2 3.

У пирамиды n=9 вершин, их значения можно разместить в массиве а, но таким образом, что следующие за вершиной из a[i] помещаются в a[2i] и a [2i+l]. Заметим, что а[6]=11, а[7]=7, а они следуют за элементом а[3]=14 (рисунок 1.10).

h=243 height=75 src="images/referats/12447/image014.jpg">

Рисунок 1.10 – Пирамида

Очевидно, что если 2i > n, тогда за вершиной a[i] не следуют другие вершины, и она является конечной вершиной пирамиды.

Процесс построения пирамиды для заданного массива можно разбить на четыре этапа:

1) меняя местами а[1] и а[n], получаем 3 9 14 8 5 11 7 2 27;

2) уменьшаем n на 1, т. е. n=n‑1, что эквивалентно удалению вершины 27 из дерева;

3) преобразуем дерево в другую пирамиду перестановкой

нового корня с большей из двух новых, непосредственно следующих за ним вершин, до тех пор, пока он не станет больше, чем обе вершины, непосредственно за ним следующие;

4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n=1.

Для алгоритма сортировки нужна процедура преобразования произвольного массива в пирамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа налево с проверкой одновременно двух условий: больше ли а[n], чем a[2i] и a [2i+l].

Полный текст программы приведен ниже.

program sortirovka_5;

(*улучшенная сортировка выбором – сортировка с помощью дерева*)

const N=8;

type item= integer;

var a: array [1 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+1;

while (j<=R) and (x<a[j]) do begin y:=a[i]; a[i]:=a[j];

a[j]:=y; a[i]:=a[j]; i:=j; j:=2*j;

if (j<R) and (a[j]<a [j+1]) then j:=j+1;

end;

end;

begin

(*задание искомого массива*)

for k:=1 to N do begin write ('Bведите элемент a [', k, ']=');

readln (a[k]);

end;

for k:=1 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:=1 to N do begin write (a[k], ' ');

end;

readln;

end.

Сортировка с помощью обменов

1‑ый вариант. Соседние элементы массива сравниваются и при необходимости меняются местами до тех пор, пока массив не будет полностью упорядочен. Повторные проходы массива сдвигают каждый раз наименьший элемент оставшейся части массива к левому его концу. Метод широко известен под названием «пузырьковая сортировка» потому, что большие элементы массива, подобно пузырькам, «всплывают» на соответствующую позицию. Основной фрагмент программы содержит два вложенных цикла, причём внутренний цикл удобнее выбрать с шагом, равным -1 [8]:

for i: =2 to n do

for j:=n downto i do

if a [j‑1]>a[j] then

begin {обмен}x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=xend;

2‑ой вариант. Пузырьковая сортировка является не самой эффективной, особенно для последовательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из которых один берется слева (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. После этого этапа возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него младшие элементы, а справа – старшие [8].

Далее подобную процедуру можно применить к левой и правой частям массива и т. д. Очевидно, что характер алгоритма рекурсивный. Для запоминания ведущих левого и правого элементов в программе необходимо использовать стек.

Характерной чертой алгоритмов сортировки с помощью обмена является обмен местами двух элементов массива после их сравнения друг с другом. В так называемой «пузырьковой сортировке» проводят несколько проходов по массиву, в каждом из которых повторяется одна и та же процедура: сравнение двух последовательно стоящих элементов и их обмен местами в порядке меньшинства (старшинства). Подобная процедура сдвигает наименьшие элементы к левому концу массива.

program sortirovka_6;

(*сортировка прямым обменом – пузырьковая сортировка*)

const N=5;

type item= integer;

var a: array [1 n] of item; i, j: integer; x: item;

begin (*задание искомого массива*)

for i:=1 to N do begin write ('введи элемент a [', i, ']= ');

readln (a[i]);

end;

for i:=1 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‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x;

end;

end;

(*вывод отсортированного массива*)

for i:=1 to N do begin write (a[i], ' ');

end;

readln;

end.

Представленную программу можно легко улучшить, если учесть, что если после очередного прохода перестановок не было, то последовательность элементов уже упорядочена, т. е. продолжать проходы не имеет смысла. Если чередовать направление последовательных просмотров, алгоритм улучшается. Такой алгоритм называют «шейкерной» сортировкой.

program sortirovka_7;

(*сортировка прямым обменом – шейкерная сортировка*)

const N=5;

type item= integer;

var a: array [1 n] of item; i, j, k, L, R: integer; x: item;

begin (*задание искомого массива*)

for i: =1 to N do begin write ('введи элемент а [', i, '] = ');

readln (a[i]);

end;

for i:=1 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‑1]; a [j‑1]:=a[j];

a[j]:=x; k:=-j

end;

end;

L:=k+1;

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‑1; until L>R;

(*вывод отсортированного массива*)

for i:=l to N do

begin write (a[i], ' ');

end;

readln;

end.

Быстрая сортировка

Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки – быстрая сортировка, предложенная Ч. Хоаром. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort [6].

 Скачать реферат