Сравнение алгоритм в сортировки

Задача №1 Сравнение алгоритм в сортировки

Сортировка перемешиванием (Шейкерная сортировка). 

 

Когда данные сортируются  не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений  элементов существенно влияет на время работы. Этот алгоритм уменьшает  количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный  и максимальный. Потом минимальный  элемент помещается в начало массива, а максимальный, соответственно, в  конец. Далее алгоритм выполняется  для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N — количество элементов. Реализация данного алгоритма выглядит так:

Приведем код программы: Program ShakerSort; uses crt; Var A       : array[1..700] of integer;     N,i,j,p    : integer;     Min, Max : integer; Begin clrscr; n:=700; {zapolnenie ishodnogo massiva} randomize;  writeln ('ishodni macciv'); for i:=1 to n do begin a[i]:=random(100);  if i<700 then write(a[i],', ') else write(a[i],'. ') end;  writeln; {sortirovka} for i:=1 to n div 2 do   begin    if A[i]>A[i+1] then    begin     Min:=i+1;     Max:=i;    end    else    begin     Min:=i;     Max:=i+1;    end;    for j:=i+2 to n-i+1 do    if A[j]>A[Max] then     Max:=j    else    if A[j]<A[Min] then     Min:=j;    {obmen alamentov}     P:=A[i];     A[i]:=A[min];     A[min]:=P;     if max=i then     max:=min;     P:=A[N-i+1];     A[N-i+1]:=A[max];     A[max]:=P;   end; {vivod alementov}   writeln ('otsortirovani macciv');   for i:=1 to n do begin   if i<700 then write(a[i],', ') else write(a[i],'. ') end;  readln; End.

Это разновидность пузырьковой сортировки. Массив просматривается поочередно справа налево и слева направо. Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

Сортировка по методу Шелла

В процессе первого прохода самостоятельно собираются и рассортировываются все  элементы, которые отстоят друг относительно друга на четыре позиции. Данный шаг  является 4-сортировкой. В рассматриваемом  примере с восьмью элементами все группы содержат ровно по два  элемента. Затем элементы снова объединяются в группы с элементами, которые  отстоят друг относительно друга  на две позиции, и рассортировываются вновь. Данный шаг является 2-сортировкой. В заключение на третьем проходе  каждый элемент сортируется простой  сортировкой или 1-сортировкой.

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

Ясно, что данный метод в итоге  формирует упорядоченный массив, и тоже совершенно понятно, что всякий проход будет применять итоги  предшествующего прохода, так как  всякая i-сортировка соединяет две  группы, отсортированные предшествующей 2i-сортировкой. Тоже понятно, что подойдет всякая последовательность приращений, только бы последнее равнялось 1, потому, что в наихудшем случае работа целиком будет исполняться на последнем проходе. Тем не менее, не так очевидно, что метод убывающего приращения выдает более лучшие результаты, в случае, если приращения не есть степени двойки.

Поэтому, программа формируется  независимо от конкретной последовательности приращений. Все t приращений условно обозначиваются как с условиями .

Всякая h-сортировка программируется  в качестве сортировки простыми включениями. И для того, чтобы условие заканчивания поиска места включения являлось простым, применяется барьер.

Понятно, что всякая h-сортировке нужен  собственный барьер, и что программе  нужно определить его место, как  можно проще. Соответственно в массив a нужно включить не одну компоненту, а [0], a компонент, так что теперь его можно описать как

uses crt;

var i, j, n, d, ch: integer;

mas: array [1..700] of integer;

begin clrscr;

n:=700;

randomize;

writeln('vvedenie alementov massiva');

for i:=1 to n do begin

mas[i]:=random(100);

write(' ', mas[i]);

end;

writeln;

d:=n;

d:=d div 2;

while (d>0) do

begin

for i:=1 to n-d do

begin

j:=i;

{poka ne dostignuto nashalo massiva i nastoiashi alament>chem element na j=1 shage }

while ((j>0) and (mas[j]>mas[j+d])) do

begin

ch:=mas[j];

mas[j]:=mas[j+d];

mas[j+d]:=ch;

j:=j-1;

end;

end;

d:=d div 2;

end;

writeln('elementi poushivshegosya massiva');

for i:=1 to n do

write(' ', mas[i]);

readln;

end.

Анализ сортировки Шелла. Анализируя этот алгоритм, приходится сталкиваться с определенными очень  сложными математическими задачами, часть из которых пока не решены.

Например, неясно, какая последовательность приращений выдает лучшие итоги. Тем  не менее, обнаружен странный принцип, в том, что они должны быть некратны друг относительно друга. Так можно  избежать ситуации, видной в приведенном  ранее примере, когда всякий проход сортировки соединяет две цепочки, которые до того никоим образом не взаимодействовавшие. В то же время  желательно, чтобы взаимодействие разных цепочек проходило как можно  чаще. Таким образом формулируется следующая теория:

В случае, когда k-рассортированная последовательность i-сортируется, тогда она по прежнему будет k-рассортированной.

В дальнейшем анализ указывает, что  в последнем случае издержки, требуемые  для сортировки n элементов при помощи алгоритма сортировки Шелла, прямо пропорциональны n^6/5. Это намного лучше по сравнению с n².

 

Задача №2 Деревья

Неупорядоченное дерево

Дерево, как математический объект – это абстракция из соименных единиц, встречающихся в природе. Схожесть структуры естественных деревьев с графами определенного вида говорит о допущении установления аналогии между ними. А именно со связанными и вместе с этим ациклическими (не имеющими циклов) графами. Последние по своему строению действительно напоминают деревья, но в чем то и имеются различия, например, принято изображать математические деревья с корнем расположенным вверху, т. е. все ветви «растут» сверху вниз. Известно же, что в природе это совсем не так.

Ввиду того что, дерево это по своей  сути граф, у него с последним  многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры. Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

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

Представление данных в рассмотренной  структуре выгодно в случае наличия  у информации явной иерархии. Например, работа с данными о биологических  родах и видах, служебных должностях, географических объектах требует иерархически выраженной структуры, такой как  математические деревья.

 

Программный код

program Project1;

uses

  Crt ;

TYPE BT=string;

     U = ^BinTree;

     BinTree = Record

         Inf : BT;

         L,R : U;

END;

 

PROCEDURE Ins(Var T : U; X : BT);

Var vsp, A : U;

Begin

    New(A); A^.Inf := X; A^.L:=Nil; A^.R := Nil;

    If T=Nil Then T:=A

                Else Begin vsp := T;

                          While vsp <> Nil Do

                           If A^.Inf < vsp^.Inf

                           Then

                            If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L

                           Else

              If vsp^.R = Nil Then Begin vsp^.R := A; vsp:=A^.R End Else vsp := vsp^.R;

                       End

END;

 

 

PROCEDURE PrintTree(T:U);

Begin

 if T<>nil then

             begin

              PrintTree(T^.L);

              Writeln('  ', T^.inf);

              PrintTree(T^.R);

             end;

END;

 

PROCEDURE Vh_E(T:U; E:BT; var i:integer);

Begin

 if T<>nil then

             begin

              Vh_E(T^.L,E,i);

              if T^.inf=E then inc(i);

              Vh_E(T^.R,E,i);

             end;

END;

 

 

PROCEDURE InsDer(var T:U);

var i,n:integer;

    x:BT;

Begin

  Randomize;

  Write('kol-vo ludei: ');

  readln(n);

  for i:=1 to n do

  begin

     write('vvedite imya: '); readln(x);

    {x:=-10+Random(21); write(x:5:3,'   '); }

    Ins(T,x);

  end;

END;

 

var Der:U;

    E:BT;

    i:integer;

 

BEGIN

  { TODO -oUser -cConsole Main : Insert code here }

  InsDer(Der);

  writeln;

  PrintTree(Der);

  write('iscomoe imya '); readln(E);

  i:=0;

  Vh_E(Der,E,i); writeln;

  writeln('Kol-vo imen: ',i);

  readln;

END.

Задача №3 Задача коммивояжера

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в неизвестном  порядке города 2,3,4..n и вернуться  в первый город. Расстояния между  городами известны. В каком порядке  следует обходить города, чтобы замкнутый  путь (тур) коммивояжера был кратчайшим?

Описание метода решения  задачи

Нужно разделить огромное число  перебираемых вариантов на классы и  получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь  возможность отбрасывать варианты не по одному, а целыми классами. Трудность  состоит в том, чтобы найти  такое разделение на классы (ветви) и такие оценки (границы), чтобы  процедура была эффективной.

-	1	2		3		4		5	6
1	-	0		0		3		3	6
2	0	-		1		4		1	0
3	1	2		-		0		0	3
4	4	5		0		-		1	3
5	4	2		0		1		-	0
6	7	1		3		3		0	-
			2		1				4
табл. 4

 

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 2

-	1	2	3	4	5	6
1	-	2	0	4	3	10	4
2	0	-	1	5	1	4	6
3	1	4	-	1	0	7	3
4	4	7	0	-	1	7	4
5	4	4	0	2	-	4	3
6	7	3	3	4	0	-	7
табл. 3