2sem / LR2_MatlabZapiska

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МВЭ

Отчет

По лабораторной работе №2

по дисциплине «Алгоритмы и вычислительные средства»

Тема:Алгоритмы и программы решения задач комбинаторики. Сортировка выбором.

Студент гр. 3206		Корепанов Д. М.
Руководитель		Шевченко С. А.

Санкт-Петербург

2024

1. Цель.

Изучение и программирование стандартного алгоритма сортировки выбором.

1. Постановка задачи.

Задан алгоритм сортировки выбором и вектор исходных данных S(n)

2. Алгоритм выполнения работы.

1. Реализовать алгоритм сортировки (по возрастанию) для вектора исходных данных S(7) в программе Matlab

2. Вставить комментарии к операторам программы

3. Вставить в программу стандартные функции tic, toc для оценки времени решения задачи.

4. Проверить программу Matlab на векторе исходных данных

5. Определить число перестановок (m) элементов вектора S(7)

6. Получить листинг отсортированного вектора S(7)

7. Модифицировать программу Matlab, задав исходный вектор S(1000). Для этого использовать функции rand и fix: s=fix(50*rand ([1 1000])); листинг отсортированного вектора выключить

8. Зафиксировать время выполнения программы (наименьшее из 20 прогонов программы) и соответствующее ему число перестановок элементов вектора

9. Повторить пункты 7-9 для векторов S(10000), S(100000). Составить в Excel таблицу из трех строк (i=1, 2, 3), включив столбики с размерностью вектора, временем выполнения сортировки и числом перестановок.

10. Рассчитать коэффициенты: KN=Nj/Ni, Kt=tj/ti, Km=mj/mi для комбинаций (i=1; j=2, 3) и (i=2; j=3). Установить закономерность изменения времени сортировки и числа перестановок от изменения размерности вектора (Kt ~ KN Km ~ KN)

11. Оформить отчет, включив в него тексты программ Matlab, листинг отсортированного вектора S(7), таблицу времени выполнения и числа перестановок от размерности вектора, таблицу с коэффициентами KN, Kt, Km

12. В выводы включить закономерность изменения времени сортировки и числа перестановок от изменения размерности вектора (Kt ~ KN Km ~ KN).

4. Основная часть.

Изображение 1 -- Блок-схема алгоритма

1. Сортировка для вектора из 7 компонентов.

   1. Код программы.

clc

clear

N=7;

M=0;

S=[10; 8; 3; 28; 11; 4; 1]; %ввод данных

tic

for I=1:(N-1); %для каждого порядка множества

MIN=I: %именнуем его минимальным

for J=(I+1):N: %сравниваем с последующим

If S(J)<S(MIN);

MIN=J %если среди последующих есть меньше - оно минимальное

end

P=dS(I);

S(I)=S(MIN);

S(MIN)=P; %меняем местами

M=M+1; %счетчик

end

end

toc

S

M

2. Листинг результатов.

Изображение 2 -- Листинг результатов сортировки

Количество итераций = 6.

2. Сортировка для больших векторов.

i	N	t, сек	M
1	1000	2.039	999
2	10000	203.063	9999
3	100000	20390.000	99999

Таблица 1 -- Прямые измерения

i-j	Kn	Kt	Km
1-2	10	99.589	10
2-3	10	100.412	10
1-3	100	10000	100

Таблица 2 -- Косвенные измерения

4. Вывод.

В ходе выполненной работы был изучен алгоритм сортировки выбором. Проведен алгоритм сортировки для больших масивов чисел и рассмотрена зависимость времени сортировки и количества итераций от количества элементов массива.

Kt - Коэффициент увеличения времени - квадратичный, равен квадрату увеличения количества элементов. При увеличении количества элементов в 10 раз, время увеличивается в 100 раз.

Km - Коэффициент увеличения итераций - линейный, равен увеличению количества элементов. При увеличении количества элементов в 10 раз, количество итераций увеличивается в 10 раз.