Лабораторная работа 4. Алгоритмы и программы решения задач комбинаторики
4.1 Алгоритм «Быстрой сортировки» (Quick Sort)
Цель: изучение и программирование стандартного алгоритма «быстрой сортировки»
Постановка задачи
Задан алгоритм сортировки выбором и вектор исходных данных S(n)
Реализовать алгоритм «быстрой» сортировки (по возрастанию) для вектора исходных данных S(7) в программе Matlab
Вставить комментарии к операторам программы
Вставить в программу стандартные функции tic, toc для оценки времени решения задачи.
Проверить программу Matlab на векторе исходных данных
Определить количество вызовов функции quicksort, используя глобальный счетчик (сm).
Получить листинг отсортированного вектора S(7)
Модифицировать программу Matlab, задав исходный вектор S(50). Для этого использовать функции rand и fix: s=fix(50*rand ([1 50])); выключить в отчет количество вызовов функции quicksort.
Определить зависимость количество вызовов функции quicksort для векторов S(80), S(100), S(150), S(200), S(250). Построить график зависимости.
Для векторов S(104), S(105), S(106), S(107) зафиксировать время выполнения программы (наибольшее из 20 прогонов программы) и соответствующее ему количество вызовов функции quicksort.
Составить в Excel таблицу из четырех строк (i=1, 2, 3, 4), включив столбики с размерностью вектора, временем выполнения сортировки и количеством вызовов функции quicksort.
Рассчитать коэффициенты: KN=Nj/Ni, Kt=tj/ti для комбинаций i-i (1-2, 1-3, 1-4). Установить закономерность изменения времени сортировки от изменения размерности вектора (Kt ~ KN)
Оформить отчет, включив в него тексты программ Matlab, листинг отсортированного вектора S(7), таблицу времени выполнения от размерности вектора, таблицу с коэффициентами KN, Kt,
В выводы включить закономерность изменения времени сортировки от изменения размерности вектора (Kt ~ KN) и закономерность изменения количества вызовов функции от размерности векторов.
-
i
N
t, сек
1
2
3
4
-
i-i
KN
Kt
1-2
1-3
1-4