Анализ сортировки деревом

5.3 Анализ сортировки деревом

Анализ сортировки деревом был проведен на примере массива длиной в 16, 128, 512, 1024 элементов.

Результаты представлены в виде нижеследующей таблицы.

Таблица 6. Результаты сортировки

Количество элементов в массиве	16	128	512	1024
Количество перестановок	18	130	514	1026

Ниже приведен график сортировки деревом.

Рисунок 3. График сортировки деревом.

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

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

Заключение

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

Список литературы

1. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983г.

2. Лавров С.С, Гончаров Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.

3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика, 2007г.

Приложение А

Таблицы идентификаторов

Таблица А.1: Идентификаторы основной программы

Имя параметра	Физический смысл параметра	Тип параметра
n	Длина исходного массива до 1024 элементов	integer
i	Счетчик, индекс элемента массива	integer
j	Счетчик, индекс элемента массива, указатель	integer
x	Искомое число	integer
a	Одномерный числовой массив (исходный массив)	mas=array [1..1024] of integer
b	Двумерный числовой массив, дерево, образованное из исходного массива	mas2=array [1..1024, 1..5] of integer
b1	Двумерный числовой массив, сортируемое дерево	mas2=array [1..1024, 1..5] of integer
F	Текстовый файл для хранения исходного массива	text
F_1	Текстовый файл для хранения отсортированного массива, сортируемого массива после каждой перестановки	text

Таблица А.2: Идентификаторы процедуры VVod

Имя параметра	Физический смысл параметра	Тип параметра
i	Счетчик, индекс элемента формируемого массива	integer
n	Длина формируемого массива	integer
a	Формируемый массив	mas=array [1..1024] of integer

Таблица А.3: Идентификаторы процедуры Vivod

Имя параметра	Физический смысл параметра	Тип параметра
i	Счетчик, индекс элемента выводимого на экран массива	integer
n	Длин массива, выводимого на экран	integer
a	Выводимый на экран массив	mas=array [1..1024] of integer

Таблица А.4: Идентификаторы процедуры Save_To_File

Имя параметра	Физический смысл параметра	Тип параметра
i1	Счетчик, индекс элемента массива, сохраняемого в файл	integer
F	Файл, в который необходимо записывать сортируемый массив после каждой перестановки	text
n	Длина массива	integer
a	Исходный массив, сохраняемый в файл	mas=array [1..1024] of integer
m	Количество перестановок	integer

А.5 Идентификаторы процедуры Lin_Poisk

Имя параметра	Физический смысл параметра	Тип параметра
i	Счетчик, индекс элемента массива	integer
k	Количество сравнений	integer
n	Длина массива	integer
a	Массив, в котором необходимо найти искомый элемент	mas=array [1..1024] of integer
x	Искомый элемент	integer

Таблица А.6 Идентификаторы процедуры Dv_Poisk

Имя параметра	Физический смысл параметра	Тип параметра
sri	Индекс среднего элемента в массиве	integer
k	Количество сравнений	integer
vi	Индекс верхнего элемента в массиве	integer
ni	Индекс нижнего элемента в массиве	integer
n	Длина массива	integer
a	Массив, в котором необходимо найти искомый элемент	mas=array [1..1024] of integer
x	Искомый элемент	integer
f	Флаг нахождения искомого элемента в массиве	boolean

Таблица А.7: Идентификаторы процедуры Tree

Имя параметра	Физический смысл параметра	Тип параметра
i	Счетчик, индекс элемента массива (строка)	integer
j	Счетчик, индекс элемента массива (столбец)	integer
s	Рабочая память, необходимая для хранения значения	integer
k	Индекс элемента в массиве	integer
a	Исходный массив, из которого следует построить дерево	mas=array [1..1024] of integer
n	Длина массива	integer
b	Дерево, полученное из массива A	mas2=array [1..1024, 1..5] of integer

Таблица А.8: Идентификаторы процедуры TreeSort

Имя параметра	Физический смысл параметра	Тип параметра
k	Число вершин дерева	integer
m	Количество перестановок	integer
i1	Счетчик, индекс элемента массива	integer
b	Дерево, полученное из массива	mas2=array [1..1024, 1..5] of integer
b1	Сортируемое дерево	mas2=array [1..1024, 1..5] of integer
a	Отсортированный массив	mas=array [1..1024] of integer

Приложение Б

Текст программы

Program Fariza_Kurs;

uses crt;

type

mas= array [1..1024] of integer;

mas2= array [1..1024, 1..5] of integer;

var n,i,j,x: integer;

a: mas;

b,b1: mas2;

f, f1: text;

Procedure Vvod(n: integer; Var a: mas);

var i: integer;

begin

if n<=16 then

begin

writeln('Vvedite elementy massiva');

for i:=1 to n do read(A[i]);

end

else

for i:=1 to n do

A[i]:=random(1000);

writeln(f,'Ishodnii masssiv');

for i:=1 to n do write(f,a[i]:4);

end;

Procedure Vivod(n: integer; a: mas);

var i: integer;

begin

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

end;

{zapis v fail}

Procedure Save_To_File(var f:text; n: integer; a: mas; m:integer);

var i1: integer;

begin

if n<=16 then

begin

writeln(f,m,'-yi shag:');

for i1:=1 to n do

write(f,A[i1]:4);

writeln(f);

end;

if (n>16) and (m mod 10=0) then

begin

writeln(f,m,'-yi shag:');

for i1:=1 to n do

write(f,A[i1]:4);

writeln(f);

end;

end;

{metod lineinogo poiska}

Procedure Lin_Poisk(n: integer; a: mas; x: integer);

var i,k: integer;

begin

writeln('Metod lineinogo poiska:');

k:=0;

for i:=1 to n do

if a[i]=x then begin k:=i; break;

end;

if k<>0 then Writeln('Element naiden. Sravnenii - ',k)

else writeln('Element ne naiden');

end;

{========metod dvoichnogo poiska ================}

procedure Dv_Poisk(n:integer;a:mas; x:integer);

var k,ni,vi, sri:integer;

f:boolean;

begin

writeln('Metod dvoichnogo poiska:');

vi:=N;

ni:=1;

k:=0;

f:=FALSE;

repeat

sri:=( (ni+vi) div 2);

k:=k+1;

if a[sri] = X then f:=TRUE

else if X > a[sri] then ni:=sri else vi:=sri;

until (k>trunc(ln(n)/ln(2))) or (f=true);

if f=true then writeln('Element naiden, Index= ', sri,'. Sravnenii ',k)

else writeln('Element ne naiden');

end;

{predstavlenie massiva A v vide dereva}

Procedure Tree(a:mas; n: integer; var b: mas2 );

label l;

var i,j,s,k: integer;

begin

b[1,3]:=0;

b[1,4]:=0;

b[1,5]:=0;

for i:=1 to n do begin

b[i,1]:=a[i];

b[i,2]:=a[i];

end;

for i:=2 to n do

begin

k:=1;

l: if b[i,1]<b[k,1] then j:=3 else j:=4;

s:=b[k,j];

if s<>0 then begin

k:=s;

goto l;

end;

b[k,j]:=i;

b[i,3]:=0;

b[i,4]:=0;

b[i,5]:=k;

end;

end;

{sortirovka derevom}

procedure Tree_Sort(b: mas2; var b1: mas2; n: integer);

label l1,l2,l3;

var k,m,i1: integer;

begin m:=0;

for i:=1 to n do

for j:=1 to 5 do

b1[i,j]:=b[i,j];

i:=1;

k:=0;

l1:

if b[i,3]<>0 then

begin

i:= b[i,3];

goto ll;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

l2:

k:=k+1;

b1[k,1]:=b[i,1];

b1[k,2]:=b[i,2];

if b[i,4]<>0 then

begin

i:=b[i,4];

goto ll;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

l3:

j:=i;

i:=b[i,5];

if i<>0 then

begin

if b[i,1]> b[j,1] then goto lm else goto ln;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

writeln('Otsortirovanii massiv');

Vivod(n,a);

readln;

writeln('Kolichestvo perestanovok=',m);

end;

BEGIN

writeln(' VVedite 4islo elementov massiva N<=1024');

readln(n);

assign (f, 'd:\dan.txt');

rewrite(f);

Vvod(n,a);

close(f);

writeln('Ishodnii massiv:');

Vivod(n,a);

{====================lineinii poisk===============}

writeln;

writeln('Vvedite element dla poiska');

readln(x);

LinPoisk(n,a,x);

{========sortirovka============}

assign (f1, 'd:\res.txt');

rewrite(f1);

tree(a,n,b);

Treesort(b,b1,n);

writeln(f1, 'Otsortirovannyi massiv:');

for i:=1 to n do write(f1, A[i]:4);

close(f1);

{========dvoichnii poisk===========}

DvPoisk(n,a,x);

end.