2.2 Применение методов
Трудно назвать какой-то метод лучшим какой-то худшим. Для каждой ситуации нужно подобрать более удобный метод. Например метод сортировки обменами легко реализовать. И если нужно упорядочить небольшое количество элементов, то он более предпочтителен.
Метод сортировки Хоара достаточно трудно реализовать. Он работает по принципу рулетки и зависит от выбора граничного элемента. При неудачном выборе граничного числа он работает медленно.
Глава 3. Графический интерфейс
3.1 Стартовое окно
Вот окно, которое представляется пользователю после запуска программы (рис.3). В этом окне он выбирает количество прямоугольников, генерирует координаты вершин. Пользователь в этом окне может построить эти прямоугольники или же отсортировать в порядке возрастания их площадей.
Рисунок 3. Стартовое окно
3.2 Построение неотсортированных прямоугольников
Если после генерирования нажать кнопку построить, то прямоугольники нарисуются в неотсортированном порядке (рис.4).
Рисунок 4. Построение неотсортированных прямоугольников
3.3 Построение отсортированных прямоугольников
Если мы отсортировали прямоугольники по площадям любым из представленных методов, то после нажатия кнопки построить программа построит их в порядке возрастания (рис.5).
Рисунок 5. Построение отсортированных прямоугольников
Заключение.
В ходе курсовой работы были выполнены следующие задачи.
Изучены алгоритмы сортировки обменами, сортировки вставками(Пузырьком), сортировки методом Хоара(Быстрая) и метода Уильямса-Флойда(Пирамидальная).
Реализованы и наглядно продемонстрированы эти методы в задаче.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
Н. Вирт Алгоритмы и структуры данных. – М.: Мир, 1939, 360 стр.
Н. Вирт Алгоритмы + структуры данных = программы. – М.: Мир, 1997, 407 стр.
Д.Кнут искусство программирования Том 3. – М:Вильямс, 2-е издание, 2002, 800 стр.
http://INTUIT .ru – Интернет-Университет Информационных Технологий
Приложения
Приложение 1. Исходный код
uses vcl, utils;
type
mas=array[0..416600] of longint;
//$VCLDESIGN+
var
Form1: Form;
TextLabel1: TextLabel;
PaintBox1: PaintBox;
Edit1: Edit;
Button1: Button;
RadioButton1: RadioButton;
RadioButton2: RadioButton;
RadioButton3: RadioButton;
RadioButton4: RadioButton;
Button2: Button;
Button3: Button;
Panel1: Panel;
//$VCLDESIGN-
X1, X2, Y1, Y2, S, A: mas;
N, i, j, dat: integer;
ts: string;
procedure InitControls;
begin
Form1:= Form.Create(0,0,877,368);
Form1.InitControl(True,False,alNone,crDefault,clBtnFace,'Форма1','');
TextLabel1:= TextLabel.Create(Form1,8,8,152,13);
TextLabel1.InitControl(True,True,alNone,crDefault,clBtnFace,'Количество прямоугольников','');
PaintBox1:= PaintBox.Create(Form1,368,16,481,297);
PaintBox1.InitControl(True,True,alNone,crDefault,0,'0','');
Edit1:= Edit.Create(Form1,168,8,65,17);
Edit1.InitControl(True,True,alNone,crDefault,clWindow,'','');
Button1:= Button.Create(Form1,248,5,75,25);
Button1.InitControl(True,True,alNone,crDefault,0,'Генерировать','');
RadioButton1:= RadioButton.Create(Form1,8,32,150,17);
RadioButton1.InitControl(True,True,alNone,crDefault,clBtnFace,'Сортировка Обменами','');
RadioButton1.PopMenu:= nil;
RadioButton2:= RadioButton.Create(Form1,8,48,150,17);
RadioButton2.InitControl(True,True,alNone,crDefault,clBtnFace,'Сортировка Вставками','');
RadioButton2.PopMenu:= nil;
RadioButton3:= RadioButton.Create(Form1,8,64,169,17);
RadioButton3.InitControl(True,True,alNone,crDefault,clBtnFace,'Сортировка методом Хоора','');
RadioButton3.PopMenu:= nil;
RadioButton4:= RadioButton.Create(Form1,8,80,233,17);
RadioButton4.InitControl(True,True,alNone,crDefault,clBtnFace,'Сортировка методом Уильямса-Флойда','');
RadioButton4.PopMenu:= nil;
Button2:= Button.Create(Form1,8,104,153,81);
Button2.InitControl(True,True,alNone,crDefault,0,'СОРТИРОВАТЬ','');
Button3:= Button.Create(Form1,168,104,153,81);
Button3.InitControl(True,True,alNone,crDefault,0,'ПОСТРОИТЬ','');
Panel1:= Panel.Create(Form1,8,192,73,41);
Panel1.InitControl(True,True,alNone,crDefault,clBtnFace,'','');
RadioButton1.Checked:= True;
Form1.Position:= poScreenCenter;
Form1.Show;
end;
procedure Rand;
begin
for i:=1 to N do
begin
X1[i]:= random(480);
X2[i]:= random(480);
Y1[i]:= random(290);
Y2[i]:= random(290);
end;
end;
procedure Space;
begin
for i:=1 to N do
begin
S[i]:=abs((X1[i]-X2[i])*(Y1[i]-Y2[i]))
end;
end;
procedure ExchangeSort( var A : mas );
var
x : integer;
begin
for i := N downto 2 do
for j := 2 to i do
if A[j] < A[j - 1] then
begin
x := A[j];
A[j] := A[j - 1];
A[j - 1] := x;
end;
end;
procedure InsertSort( var A : mas );
var
i, k : Integer;
x : integer;
begin
{ Вставляем в уже отсортированную часть элементы со 2 по max }
for i := 2 to N do
begin
k := i;
x := A[i];
{ Передвигаем на 1 позицию направо элементы,
большие вставляемого элемента (он записан в x) }
while (A[k - 1] > x) do
begin
A[k] := A[k - 1];
k := k - 1;
end;
{ Вставляем элемент в нужную позицию }
A[k] := x;
end;
end;
Procedure PiramidaSort(var A: mas);
Var t, k, i, Y: Integer;
Begin
For i := 2 to N do { создание структуры бинарного дерева-"пирамиды" }
begin
t := i;
while t <> 1 do
begin k := t div 2;
If A[k] >= A[t] then t := 1
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k;
end
end
end;
For i := N-1 downto 1 do { сортировка массива-"пирамиды" }
begin
Y:=A[i+1]; A[i+1]:=A[1]; A[1]:=Y;
t := 1;
While t <> 0 do
begin
k := t+t;
If k > i then t := 0
else
begin
If k < i then If A[k+1] > A[k] then k := k+1;
If A[t] >= A[k] then t := 0
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k
end;
end;
end;
end;
End;
{ Процедура разбиения массива для быстрой сортировки }
function Partition( var A : mas; l, r : Integer; x : integer ) : Integer;
{ Переставляем элементы массива так, чтобы слева от элемента,
равного x, были только элементы меньшие или равные x,
а справа - элементы, большие или равные x }
var
i, j : Integer;
t : integer;
begin
i := l - 1;
j := r + 1;
repeat
{ Пока элементы справа больше среднего }
repeat
j := j - 1;
until x >= A[j];
{ Пока элементы слева меньше среднего }
repeat
i := i + 1;
until A[i] >= x;
{ Меняем левый и правый элементы и продолжаем дальше }
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
{ Иначе - левый и правый встретились -
разбиение массива завершено }
until i >= j;
Partition := j;
end;
{ Рекурсивная процедура быстрой сортировки }
procedure RecoursiveQuick( var A : mas; l, r : Integer );
var
m : Integer;
begin
if l < r then
begin
{ В качестве граничного элемента выбирается средний
элемент массива }
m := Partition(A, l, r, A[(l + r) div 2]);
RecoursiveQuick(A, l, m);
RecoursiveQuick(A, m + 1, r);
end;
end;
{ Быстрая сортировка }
procedure QuickSort( var A : mas );
begin
RecoursiveQuick(A, 1, N);
end;
procedure Generation;
begin
val(edit1.text, N, i);
rand;
Space;
for i:=1 to N do
A[i]:=S[i];
end;
procedure Exchange;
begin
for i:=1 to N do
A[i]:=S[i];
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
ExchangeSort(A);
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
str(dat,ts);
panel1.caption:=ts+'мc';
end;
procedure Insert;
begin
for i:=1 to N do
A[i]:=S[i];
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
InsertSort(A);
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
str(dat,ts);
panel1.caption:=ts+'мc';
end;
procedure Piramida;
begin
for i:=1 to N do
A[i]:=S[i];
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
PiramidaSort(A);
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
str(dat,ts);
panel1.caption:=ts+'мc';
end;
procedure Quick;
begin
for i:=1 to N do
A[i]:=S[i];
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
QuickSort(A);
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
str(dat,ts);
panel1.caption:=ts+'мc';
end;
procedure Sort;
begin
if radiobutton1.checked=true then Exchange;
if radiobutton2.checked=true then Insert;
if radiobutton3.checked=true then Quick;
if radiobutton4.checked=true then Piramida;
end;
procedure Build;
begin
for j:=N downto 1 do
for i:=N downto 1 do
if A[j]= S[i] then
begin
paintbox1.rectangle(X1[i],Y1[i],X2[i],Y2[i]);
paintbox1.floodfill((X1[i]+X2[i]) div 2,(Y1[i]+Y2[i]) div 2,random(65000));
end;
end;
begin
InitControls;
button1.onclick:= Generation;
button2.onclick:= Sort;
button3.onclick:= Build;
end.
Приложение 2. Вспомогательная программа
uses utils;
const R= 50000;
type
mas=array[0..416600] of longint;
var A:mas;
i, j, k : integer;
N, dat: longint;
procedure Rand;
begin
for i:=1 to N do
A[i]:=random(R);
end;
procedure ExchangeSort;
var
x : integer;
begin
for i := N downto 2 do
for j := 2 to i do
if A[j] < A[j - 1] then
begin
x := A[j];
A[j] := A[j - 1];
A[j - 1] := x;
end;
end;
procedure InsertSort;
var
i, k : Integer;
x : integer;
begin
{ Вставляем в уже отсортированную часть элементы со 2 по max }
for i := 2 to N do
begin
k := i;
x := A[i];
{ Передвигаем на 1 позицию направо элементы,
большие вставляемого элемента (он записан в x) }
while (A[k - 1] > x) do
begin
A[k] := A[k - 1];
k := k - 1;
end;
{ Вставляем элемент в нужную позицию }
A[k] := x;
end;
end;
Procedure PiramidaSort;
Var t, k, i, Y: Integer;
Begin
For i := 2 to N do { создание структуры бинарного дерева-"пирамиды" }
begin
t := i;
while t <> 1 do
begin k := t div 2;
If A[k] >= A[t] then t := 1
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k;
end
end
end;
For i := N-1 downto 1 do { сортировка массива-"пирамиды" }
begin
Y:=A[i+1]; A[i+1]:=A[1]; A[1]:=Y;
t := 1;
While t <> 0 do
begin
k := t+t;
If k > i then t := 0
else
begin
If k < i then If A[k+1] > A[k] then k := k+1;
If A[t] >= A[k] then t := 0
else
begin
Y:=A[k]; A[k]:=A[t]; A[t]:=Y;
t := k
end;
end;
end;
end;
End;
{ Процедура разбиения массива для быстрой сортировки }
function Partition( l, r : Integer; x : integer ) : Integer;
{ Переставляем элементы массива так, чтобы слева от элемента,
равного x, были только элементы меньшие или равные x,
а справа - элементы, большие или равные x }
var
i, j : Integer;
t : integer;
begin
i := l - 1;
j := r + 1;
repeat
{ Пока элементы справа больше среднего }
repeat
j := j - 1;
until x >= A[j];
{ Пока элементы слева меньше среднего }
repeat
i := i + 1;
until A[i] >= x;
{ Меняем левый и правый элементы и продолжаем дальше }
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
{ Иначе - левый и правый встретились -
разбиение массива завершено }
until i >= j;
Partition := j;
end;
{ Рекурсивная процедура быстрой сортировки }
procedure RecoursiveQuick( l, r : Integer );
var
m : Integer;
begin
if l < r then
begin
{ В качестве граничного элемента выбирается средний
элемент массива }
m := Partition(l, r, A[(l + r) div 2]);
RecoursiveQuick( l, m);
RecoursiveQuick( m + 1, r);
end;
end;
{ Быстрая сортировка }
procedure QuickSort;
begin
RecoursiveQuick( 1, N);
end;
begin
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
ExchangeSort;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
InsertSort;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
PiramidaSort;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute;
QuickSort;
dat:=currentdatetime.milliseconds+1000*currentdatetime.second+60000*currentdatetime.minute-dat;
write(dat, ' ');
end;
writeln;
end.