Автор: Пользователь скрыл имя, 17 Февраля 2012 в 16:31, курсовая работа
Цель моей работы: оценить эффективность методов сортировки обменами, вставка-ми, метода Хоара и метода Уильмса-Флойда.
Для достижения поставленной цели необходимо решить следующие задачи:
1) Изучить алгоритмы сортировки обменами, сортировки вставками(Пузырьком), сортировки методом Хоара(Быстрая) и метода Уильямса-Флойда(Пирамидальная).
2) Реализовать и наглядно продемонстрировать эти методы в следующей задаче:
1. Сгенерировать N пар точек (x1, y1) и (x2, y2) случайным образом.
2. Вычислить площади прямоугольников, построенных по этим парам точек. Прону-меровать эти прямоугольники.
3. Отсортировать эти прямоугольники по возрастанию площади. Использовать сорти-ровку обменами, вставками, метод Хоара, метод Уильямса-Флойда.
4. Оценить эффективность этих методов для большого количества элементов, изме-рив время работы.
5. *Построить прямоугольники, закрашенные разным цветом.
Введение ………...…………...…………………………………………………..………………3
Глава 1. Алгоритмы сортировок
1.1 Сортировка методом обмена.……………………………………………..…………… 5
1.2 Сортировка с помощью выбора…………………………………………………………6
1.3 Сортировка методом Хоара ………………………………………...…………………. 7
1.4 Сортировка методом Уильямса-Флойда……...………………………………………..9
Глава 2. Эффективность методов
2.1 Сравнение методов сортировки………………………………………………………..12
2.2 Применение методов……………………………………………………………………14
Глава 3. Графический интерфейс
3.1 Стартовое окно………………………………………………………………………… 15
3.2 Построение неотсортированных прямоугольников.………………..………………… 15
3.3 Сортировка отсортированных прямоугольников…………………………………… 16
Заключение …………………....………………………………………………………………. 17
Библиографический список …………………………………………………...………….….. 18
Приложения…...………………………………………………………………………………...
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.
ExchangeSort;
dat:=currentdatetime.
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.
InsertSort;
dat:=currentdatetime.
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.
PiramidaSort;
dat:=currentdatetime.
write(dat, ' ');
end;
writeln;
for k:=1 to 20 do
begin
N:= 1000*k;
rand;
dat:=currentdatetime.
QuickSort;
dat:=currentdatetime.
write(dat, ' ');
end;
writeln;
end.