МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра МВЭ
Отчет
По лабораторной работе №2
по дисциплине «Алгоритмы и вычислительные средства»
Тема:Алгоритмы и программы решения задач комбинаторики. Сортировка выбором.
Студент гр. 3206 |
|
Корепанов Д. М. |
Руководитель |
|
Шевченко С. А. |
Санкт-Петербург
2024
Цель.
Изучение и программирование стандартного алгоритма сортировки выбором.
Постановка задачи.
Задан алгоритм сортировки выбором и вектор исходных данных S(n)
Алгоритм выполнения работы.
Реализовать алгоритм сортировки (по возрастанию) для вектора исходных данных S(7) в программе Matlab
Вставить комментарии к операторам программы
Вставить в программу стандартные функции tic, toc для оценки времени решения задачи.
Проверить программу Matlab на векторе исходных данных
Определить число перестановок (m) элементов вектора S(7)
Получить листинг отсортированного вектора S(7)
Модифицировать программу Matlab, задав исходный вектор S(1000). Для этого использовать функции rand и fix: s=fix(50*rand ([1 1000])); листинг отсортированного вектора выключить
Зафиксировать время выполнения программы (наименьшее из 20 прогонов программы) и соответствующее ему число перестановок элементов вектора
Повторить пункты 7-9 для векторов S(10000), S(100000). Составить в Excel таблицу из трех строк (i=1, 2, 3), включив столбики с размерностью вектора, временем выполнения сортировки и числом перестановок.
Рассчитать коэффициенты: KN=Nj/Ni, Kt=tj/ti, Km=mj/mi для комбинаций (i=1; j=2, 3) и (i=2; j=3). Установить закономерность изменения времени сортировки и числа перестановок от изменения размерности вектора (Kt ~ KN Km ~ KN)
Оформить отчет, включив в него тексты программ Matlab, листинг отсортированного вектора S(7), таблицу времени выполнения и числа перестановок от размерности вектора, таблицу с коэффициентами KN, Kt, Km
В выводы включить закономерность изменения времени сортировки и числа перестановок от изменения размерности вектора (Kt ~ KN Km ~ KN).
Основная часть.
Изображение 1 -- Блок-схема алгоритма
Сортировка для вектора из 7 компонентов.
Код программы.
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 -- Листинг результатов сортировки
Количество итераций = 6.
Сортировка для больших векторов.
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 -- Косвенные измерения
Вывод.
В ходе выполненной работы был изучен алгоритм сортировки выбором. Проведен алгоритм сортировки для больших масивов чисел и рассмотрена зависимость времени сортировки и количества итераций от количества элементов массива.
Kt - Коэффициент увеличения времени - квадратичный, равен квадрату увеличения количества элементов. При увеличении количества элементов в 10 раз, время увеличивается в 100 раз.
Km - Коэффициент увеличения итераций - линейный, равен увеличению количества элементов. При увеличении количества элементов в 10 раз, количество итераций увеличивается в 10 раз.