close

Вход

Забыли?

вход по аккаунту

?

Лаба на эффективность

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего профессионального образования "САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ"
КАФЕДРА АЭРОКОСМИЧЕСКИХ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
Доц., к.т.н.Коренева Е.А.должность, уч. степень, званиеподпись, датаинициалы, фамилия
ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №4НА ТЕМУ: Оценка эффективности методов сортировки.по дисциплине: ПРОГРАММИРОВАНИЕ. БАЗОВЫЕ АЛГОРИТМЫ.РАБОТУ ВЫПОЛНИЛ(А)
СТУДЕНТ(КА) ГР.134221.12.13Чередников М.Вподпись, датаинициалы, фамилия
Санкт-Петербург 2013
1. Постановка задачи: оценить эффективность различных методов сортировки.
2.Формализация задачи: * Рассмотрим 3 различных способа заполнения массива : прямой, обратный и random.
* Кол-во элементов в исходном массиве от 5000 до 30000 , сортировки будем производить по возрастанию, а так же замерять время сортировок.
а) Метод сортировки Шелла
б) Стандартный обмен
в) Стандартный обмен с флажком
* По результатам полученных замеров строим графики в осях T(N).
* Схемы алгоритмов должны быть структурированы.
3. Схема алгоритма:
А) Метод сортировки Шелла.
Б)Стандартного обмена.
В) Стандартного обмена с флажком.
4. Программа:
А) Метод сортировки Шелла (c=N*log2N).
program shell;
uses
system;
const
n = 30000;
type
mas = array[1..n] of integer;
var
a: mas;
i, k, j, h: integer;
t1, t2: DateTime;
begin
for i := 1 to n do
A[i] := {Либо i,либо N-i+1 , либо random(N)};
t1 := DateTime.Now;
k := N div 2; while k > 0 do
begin
for i := 1 to N - k do
begin
j := i;
while (j >= 1) and (a[j] > a[j + k]) do begin
h := a[j];
a[j] := a[j + k];
a[j + k] := h;
dec(j);
end;
end;
k := k div 2;
end;
t2 := DateTime.Now;
for i := 1 to n do
write(A[i], ' ');
writeln;
writeln('Время выполнения: ', (t2.Hour - t1.Hour) * 3600 + (t2.Minute - t1.Minute) * 60 + (t2.Second - t1.Second));
end.
Б) Стандартного обмена (c=n2/2).
program standobmen;
uses
system;
const
n = 30000;
type
mas = array[1..n] of integer;
var
a: mas;
i, j, k: integer;
t1, t2: DateTime;
begin
for i := 1 to n do
A[i] := {Либо i,либо N-i+1 , либо random(N)};
t1 := DateTime.Now;
for i := 1 to n - 1 do
for j := 1 to n - i do
if A[j+1] < A[j] then
begin
k := A[j];
A[j] := A[j+1];
A[j+1] := k;
end;
t2 := DateTime.Now; for i := 1 to N do
write(A[i], ' ');
writeln;
writeln('Время выполнения: ', (t2.Hour - t1.Hour) * 3600 + (t2.Minute - t1.Minute) * 60 + (t2.Second - t1.Second));
end.
В) Стандартного обмена с флажком (c=n2/2).
program standsflag;
uses
system;
const
N = 30000;
type
mas = array[1..N] of integer;
var
a: mas;
F, j, i, S: integer;
t1, t2: DateTime;
begin
for i := 1 to N do
A[i] := {Либо i,либо N-i+1 , либо random(N)};
t1 := DateTime.Now;
repeat
F := 0;
for i := 1 to N - 1 do
begin
for j := 1 to n - i do
if A[j] > A[j + 1] then
begin
s := A[j];
A[j] := A[j + 1];
A[j + 1] := s;
F := 1;
end;
end;
until F = 0;
t2 := DateTime.Now;
for i := 1 to n do
write(A[i], ' ');
writeln;
writeln('Время выполнения: ', (t2.Hour - t1.Hour) * 3600 + (t2.Minute - t1.Minute) * 60 + (t2.Second - t1.Second));
end.
5. Графики эффективности:
А)Упорядоченное заполнение массива:
Б)Обратное заполнение массивВ) Заполнение массива датчиком случайных чисел:
Документ
Категория
Рефераты
Просмотров
33
Размер файла
240 Кб
Теги
эффективность, лаба
1/--страниц
Пожаловаться на содержимое документа