МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра физической электроники и технологии
ОТЧЕТ по лабораторной работе №4
по дисциплине «Информационные технологии» Тема: Алгоритмы и программы решения задач комбинаторики
Студентка гр. 0207 |
|
Лиоско Е.П. |
|
Преподаватель |
|
|
Рябцев И.А. |
Санкт-Петербург
2021
Алгоритм «Быстрой сортировки» (Quick Sort)
Цель работы.
Изучение и программирование стандартного алгоритма «быстрой сортировки»
Блок-схема программы.
2
Текст программы 1 s(7).
clear all; clc; global cm; cm=0;
N=7;
s=[10 8 3 28 11 4 1]; tic;
y=quicksort(s);
toc;
disp(s);
disp(y); disp (cm);
function[vector]=quicksort(vector)
if ~isempty(vector)% если вектор пустой, программа остановится
global cm; cm=cm+1; pivot=vector(1);
A1=quicksort(vector(vector<pivot));
A2=vector(vector==pivot);
A3=quicksort(vector(vector>pivot)); vector=[A1 A2 A3];
end end
Листинг 1 s(7).
Elapsed time is 0.007904 seconds.
10 |
8 |
3 |
28 |
11 |
4 |
1 |
1 |
3 |
4 |
8 |
10 |
11 |
28 |
7 |
|
|
|
|
|
|
Текст программы 2 s(50).
clear all; clc;
N=50;
s=fix(50*rand ([1 50])); tic;
y=quicksort(s);
toc;
function[vector]=quicksort(vector)
3
if ~isempty(vector)% если вектор пустой, программа остановится
global cm; cm=cm+1; pivot=vector(1);
A1=quicksort(vector(vector<pivot));
A2=vector(vector==pivot);
A3=quicksort(vector(vector>pivot)); vector=[A1 A2 A3];
end end
Листинг 2 s(50).
Elapsed time is 0.011090 seconds.
Текст программы 3 s(80), s(100), s(150), s(200), s(250).
clear all; clc; global cm; cm=0; N=80; %N=100; %N=150; %N=200; %N=250;
s=fix(50*rand ([1 80])); %s=fix(50*rand ([1 100])); %s=fix(50*rand ([1 150])); %s=fix(50*rand ([1 200])); %s=fix(50*rand ([1 250])); tic;
y=quicksort(s);
toc;
disp (cm);
function[vector]=quicksort(vector)
if ~isempty(vector)% если вектор пустой, программа остановится
global cm; cm=cm+1; pivot=vector(1);
A1=quicksort(vector(vector<pivot));
A2=vector(vector==pivot);
A3=quicksort(vector(vector>pivot));
4
vector=[A1 A2 A3]; end
end
График зависимости количества вызовов функции quicksort для векторов s(80), s(100), s(150), s(200), s(250).
cm 50
49 |
|
|
|
|
48 |
|
|
|
|
47 |
|
|
|
|
46 |
|
|
|
|
45 |
|
|
|
|
44 |
|
|
|
|
43 |
|
|
|
|
42 |
|
|
|
|
41 |
|
|
|
|
40 |
|
|
|
N |
80 |
130 |
180 |
230 |
Текст программы 4 s(104), s(105), s(106), s(107).
clear all; clc; global cm; cm=0;
N=10^4;%N=10^5 %N=10^6 %N=10^7 s=fix(50*rand ([1 N]));
tic;
y=quicksort(s);
toc;
disp (cm);
function[vector]=quicksort(vector)
if ~isempty(vector)% если вектор пустой, программа остановится
global cm; cm=cm+1; pivot=vector(1);
A1=quicksort(vector(vector<pivot));
A2=vector(vector==pivot);
5