Тема 2. Основная цель этой курсовой работы сравнение и анализ алгоритмов сортировки списка прямым выбором. 4
 Скачать 0.84 Mb.
|
Приложение АКОД ПРОГРАММЫ (обязательное) unit Unit1; interface uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.Grids, Vcl.StdCtrls, Vcl.ComCtrls, VclTee.TeeGDIPlus, VCLTee.TeEngine, Vcl.ExtCtrls, VCLTee.TeeProcs, VCLTee.Chart, VCLTee.Series; type TForm1 = class(TForm) PageControl1: TPageControl; TabSheet1: TTabSheet; TabSheet2: TTabSheet; TabSheet3: TTabSheet; Label1: TLabel; Edit1: TEdit; RadioButton1: TRadioButton; RadioButton2: TRadioButton; RadioButton3: TRadioButton; Button1: TButton; Button2: TButton; Button3: TButton; StringGrid1: TStringGrid; Chart1: TChart; Label2: TLabel; Label3: TLabel; Series1: TLineSeries; Series2: TLineSeries; Label4: TLabel; Label5: TLabel; procedure Button3Click(Sender: TObject); procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure Button2Click(Sender: TObject); private { Private declarations } public { Public declarations } end; const n=1000000; var Form1: TForm1; M: array[0..n] of longint; M2: array [0..n] of longint; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); var i,j,razm,max,min,buf: longint; t,t1,t2,t3,t4,q: integer; time1: array [0..10] of integer;//Время классической сортировки массива в зависимости от его размерности time2: array [0..10] of integer;//Время сортировки массива с одновременным поиском min и max в зависимости от его размерности size: array [0..10] of longint; //Массив с размерностями массивов begin //Проверки на заполненность данных //проверка на выбранность степени упорядоченности if (RadioButton1.Checked=false) and (RadioButton2.Checked=false) and (RadioButton3.Checked=false) then Showmessage ('Необходимо выбрать степень упорядоченности!'); //Проверка на пустоту размерности массива, если пользователь //Не ввел размерность массива, то выводится соответствующее окно if length(edit1.text)=0 then Showmessage('Необходимо указать размерность массива!') else razm:=strtoint(Edit1.Text); //Присваиваем переменной размерность массива //Определяем, какой массив выбран, создаем его и дублируем эти значения во второй массив if (RadioButton1.Checked=true) then //Неупорядоченный массив begin randomize; for i:=0 to razm do begin M[i]:=random(1000000); M2[i]:=M[i]; end; end else if (RadioButton2.Checked=true) then //Упорядоченный массив begin M[0]:=random(3); for i:=1 to razm do begin M[i]:=M[i-1]+random(5)+1; M2[i]:=M[i]; end; end else if (RadioButton3.Checked=true) then //Упорядоченный в обратном порядке массив begin M[0]:=999999; for i:=1 to n do begin M[i]:=M[i-1]-random(10)-1; M2[i]:=M[i]; end; end; //В зависимости от того, какая выбрана упорядоченность, для удобства записываем это в таблицу if (RadioButton1.Checked=true) then StringGrid1.Cells[0, 4] := 'Неупорядоченный' else if (RadioButton2.Checked=true) then StringGrid1.Cells[0, 4] := 'Упорядоченный' else if (RadioButton3.Checked=true) then StringGrid1.Cells[0, 4] := 'Упорядоченный в обратном порядке'; //Сортировка классическим прямым выбором q:=0; while q<>10 do begin //Цикл необходимый для отметки времен и размерностей массивов size[q]:=razm; //Присваиваем массиву с размерностями определенные значения t1:=GetTickCount; for i:=0 to razm do begin //Цикл с выполнением классической сортировки min:=i; //Присваивается индекс первой неотсортированной переменной for j := i+1 to razm do begin //Среди оставшихся неотсортированных элементов массива находится минимальный if M[min]>M[j] then min:=j; end; buf:=M[i]; //Через дополнительную переменную меняем элементы местами M[i]:=M[min]; M[min]:=buf; end; t2:=GetTickCount; time1[q]:=t2-t1; //Заносим полученное время сортировки в массив с временными показателями q:=q+1; //Уменьшаем размерность массива if razm div 100000>=3 then razm:=razm-100000 else if razm div 100000>=1 then razm:=razm-30000 else if razm div 10000>=1 then razm:=razm-7000 else if razm div 1000>=1 then razm:=razm-200; //Возвращаем массиву первоначальный вид, но уже с уменьшенной размерностью for i:=0 to razm do M[i]:=M2[i]; end; razm:=strtoint(Edit1.Text); //Присваиваем максимальную размерность массива //Возвращаем массиву первоначальный вид с максимальной размерностью for i:=0 to razm do M[i]:=M2[i]; //Сортировка прямым выбором с одновременным поиском минимума и максимума q:=0; while q<>10 do begin //Цикл необходимый для отметки времен и размерностей массивов t3:=GetTickCount; for i:=0 to razm do begin //Цикл с выполнением сортировки с одновременным поиском минимума и максимума min:=i; //Присваивается индекс первой неотсортированной переменной max:=razm-i; //Присваивается индекс последней неотсортированной переменной for j := i+1 to razm-i-1 do begin //Среди оставшихся неотсортированных элементов if M2[min]>M2[j] then //массива находится минимальный и максимальный соответственно min:=j; if M2[max] max:=j; end; buf:=M2[i]; //Через дополнительную переменную меняем элементы местами M2[i]:=M2[min]; M2[min]:=buf; //Меняем местами первый неупорядоченный элемент с минимальным buf:=M2[razm-i]; M2[razm-i]:=M2[max]; //Меняем местами последний неупорядоченный элемент с максимальным M2[max]:=buf; end; t4:=GetTickCount; time2[q]:=t4-t3; //Заносим полученное время сортировки в массив с временными показателями q:=q+1; //Уменьшаем размерность массива if razm div 100000>=3 then razm:=razm-100000 else if razm div 100000>=1 then razm:=razm-30000 else if razm div 10000>=1 then razm:=razm-7000 else if razm div 1000>=1 then razm:=razm-200; //Возвращаем массиву первоначальный вид, но уже с уменьшенной размерностью for i:=0 to razm do begin M2[i]:=M[i]; end; end; // Занесение в таблицу временные показатели сортировок прямым выбором и соответствующие размерности for q := 0 to 9 do begin StringGrid1.Cells[1+q, 0] :=inttostr(size[q]); //Заполняем строчку в таблице с размерностями StringGrid1.Cells[1+q, 1] :=inttostr(time1[q]); //Время выполнения классической сортировки StringGrid1.Cells[1+q, 2] :=inttostr(time2[q]); //Время выполнения сортировки с одновременныс поиском min и max end; end; procedure TForm1.Button2Click(Sender: TObject); //Создание и выведение графика var i,n:integer; begin series1.Clear; series2.Clear; n:=10; for i := 1 to n do begin //Функция классической сортировка series1.AddXY(StrToInt(stringgrid1.Cells[i, 0]), StrToInt(stringgrid1.Cells[i, 1])); //Функция сортировки с поиском минимумом и максимумом series2.AddXY(StrToInt(stringgrid1.Cells[i, 0]), StrToInt(stringgrid1.Cells[i, 2])); end; end; procedure TForm1.Button3Click(Sender: TObject); //Кнопка закрытия программы begin close; end; procedure TForm1.FormCreate(Sender: TObject); //Подписываем все названия строчек в таблице begin StringGrid1.ColWidths[0] := 350; StringGrid1.RowHeights[0] := 40; StringGrid1.RowHeights[1] := 40; StringGrid1.RowHeights[2] := 40; StringGrid1.Cells[0, 0] := 'Размерность массива'; StringGrid1.Cells[0, 3] := 'Степень упорядоченности массива:'; StringGrid1.Cells[0, 1] := 'Классическая сортировка прямым выбором'; StringGrid1.Cells[0, 2] := 'Сортировка с одновременным поиском min и max'; end; end. |