Алгоритма и программы решения задач комбинаторики. Алгоритм «Быстрой сортировки»

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра радиотехнической электроники

ОТЧЕТ

по лабораторной работе №4

по дисциплине «Информационные технологии»

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

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

2022

Цель работы: изучение и программирование стандартного алгоритма сортировки «быстрой сортировки».

Приведенная блок-схема алгоритма сортировки вставкой:

[pic 1]

Рис. 1 – блок-схема, данная на этапе постановки задачи.

Код программы, написанной по данной блок-схеме, сортирующая вектор по возрастанию с помощью алгоритма сортировки вставкой:

global cm;

cm = 0;

n=input('длина вектора s');

s = randi([0 n*10], 1, n);%вектор длины n заполняется случайными числами в заданном диапазоне

disp('вектор-')

disp(s);

tic

y = quicksort(s);%вызов функции

toc

disp('отсортированный вектор-')

disp(y);

disp('кол-во раз, которые была вызвана функция')

disp(cm);

function[vector] = quicksort(vector)%функция для быстрой сортировки

global cm;

cm = cm + 1;

if length(vector)<2

    return;

end

pivot = vector(1);%сам алгоритм "быстрой сортировки"

A1 = quicksort(vector(vector<pivot));

A2 = vector(vector==pivot);

A3 = quicksort(vector(vector>pivot));

vector = [A1 A2 A3];

end

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

Задайте длину вектора 10

    59    78    39    61    24    29     1    35    14    41

Elapsed time is 0.004574 seconds.

Остортированный вектор s: 1  14  24  29  35  39  41  59  61  78

Функция быстрой сортировки была вызвана 13 раз

Рис. 2 – листинг результатов выполненной программы, сортирующей вектор по возрастанию.

Получим график зависимости количества вызовов функции от размера вектора n:

[pic 2]

Рис. 4 – график зависимости количества вызовов функции от размера веткора n

Изучим зависимость времени работы программы (t) и количества вызовов программы (m) от длины заданного вектора (N):