Министерство образования Республики Беларусь
Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники»
Факультет компьютерных систем и сетей
Кафедра программного обеспечения информационных технологий
Дисциплина: Основы алгоритмизации и программирования (ОАиП)
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
на тему:
«Сравнительный анализ сортировок прямой выбор, шейкерная и Quicksort»
БГУИР КП 1-40 01 01 5910030 ПЗ
Студент: гр. 591051 Янчуков А.В.
Руководитель: асс. Болтак С.В.
Минск 2016
Учреждение образования
«Белорусский государственный университет информатики и радиоэлектроники»
Факультет компьютерных систем и сетей
УТВЕРЖДАЮ
Заведующий кафедрой ПОИТ
––––––––––––––––––––––––
(подпись)
Лапицкая Н.В. 2016 г.
ЗАДАНИЕ
по курсовому проектированию
Студенту
–––––––––––––
1. Тема работы ––––
2. Срок сдачи студентом законченной работы 23.05.2016
3. Исходные данные к работе .
4. Содержание расчётно-пояснительной записки (перечень вопросов, которые подлежат разработке)
Введение.
1.Аналитический обзор литературы и существующих аналогов;
2.Разработка алгоритма;
3. Разработка программного средства;
4. Обоснование технических приемов программирования;
5. Тестирование, экспериментальные исследования и анализ полученных результатов;
6. Руководство пользователя программы;
Заключение, список литературы, ведомость, приложения.
5. Перечень графического материала (с точным обозначением обязательных чертежей и графиков)
1. Схема программы
6. Консультант по курсовому проекту Болтак С.В.
7. Дата выдачи задания 15.02.2016 г.–– –
8. Календарный график работы над проектом на весь период проектирования (с обозначением сроков выполнения и процентом от общего объёма работы):
раздел 1, введение к 02.03.2016 – 10 % готовности работы;
разделы 2 к 15.03.2016 – 30 % готовности работы;
разделы 3,4 к 15.04.2016 – 60 % готовности работы;
раздел 5, 6 к 05.05.2016 – 90 % готовности работы;
оформление пояснительной записки и графического материала к 20.05.2016 – 100 % готовности работы.
Защита курсового проекта с 23.05 по 12.06 2016 г.
РУКОВОДИТЕЛЬ С.В. Болтак
(подпись)
Задание принял к исполнению –––____–– 15.02.2016 г.
(дата и подпись студента)
Содержание.
Введение
5
1. Аналитический обзор существующих аналогов 6
2. Сортировка прямым выбором 8
2.1. Разработка алгоритма сортировки прямым выбором 8
2.2. Алгоритм сортировки прямым выбором 9
2.3. Текст процедуры сортировки прямым выбором 10
3. Шейкерная
сортировка
11
3.1. Разработка алгоритма шейкерной сортировки 11
3.2. Алгоритм шейкерной сортировки 12
3.3. Текст процедуры шейкерной сортировки 13
4. Быстрая
сортировка
14
3.1. Разработка алгоритма быстрой сортировки 14
3.2. Алгоритм быстрой сортировки 16
3.3. Текст процедуры быстрой сортировки 17
5. Графическая работа 18
6. Расчет времени выполнения сортировки 20
7. Обоснование технических проемов программирования 23
8. Системны требования 25
9. Инструкция пользователя 26
10. Тестирование программы 28
11. Анализ полученных результатов 29
Заключение 35
Литература 36
Приложение А
37
ВВЕДЕНИЕ
Сортировка – это процесс упорядочения множества подобных информационных объектов в некотором определённом порядке с целью облегчения последующего поиска нужных элементов.
Под сортировкой в программировании чаще всего понимается такая перестановка предметов, при которой они располагаются в порядке возрастания или убывания.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа чаще всего выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Прежде, чем изучать методы сортировки, следует ввести некоторые понятия и обозначения. Пусть имеются элементы
а1, a2, …… , аn
то сортировка есть перестановка этих элементов в массив
аk1, ak2, …… ,akn
где
ak1 <= ak2 <= ….. <= akn.
Каждый из алгоритмов сортировки имеет и свои достоинства, и свои недостатки, поэтому при сортировке выбирать алгоритм нужно, исходя из конкретной постановки задачи.
В качестве оценки методов сортировки удобно использовать понятие экономичности, т. е. время их работы. Мерой эффективности в данном случае служит:
C – число необходимых сравнений ключей и
M – число пересылок (перестановок) элементов.
Методы сортировки делятся на три типа:
1. методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;
2. методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
3. и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
1. Аналитический обзор существующих аналогов
В настоящее время существует множество алгоритмов сортировки массивов, которые применяются в зависимости от того какие условия функционирования стоят перед разрабатываемой программой.
1. Методы вставки. Алгоритм простых вставок.
1.1. Бинарные вставки
1.2. Двухпутевые вставки
1.3. Вставки одновременно нескольких элементов.
1.4. Вставки с убывающим шагом (метод Шелла)
1.5. Вставки в связанный список
1.6. Вставки в несколько связанных списков
2. Обменная сортировка
2.1. Метод пузырька
2.2. Модификация метода пузырька
2.3. Быстрая сортировка.
2.4. Обменная поразрядная сортировка
2.5. Параллельная сортировка Бэтчера
3. Сортировка посредством выбора
( Использование связанного списка для хранения
информации о промежуточных максимумах.)
4. Сортировка посредством слияния
В текущей работе ставится задача сравнить между собой три типа сортировки:
1. Сортировка прямым выбором
2. Быстрая сортировка
3. Шейкерная сортировка
Для этого нужно провести сравнительный анализ по следующим параметрам: подсчитать количество перестановок и сравнений элементов заданных массивов, а также исследовать время работы каждой сортировки при заданных параметрах. Результаты измерений оформить в виде таблиц.
По полученным результатам построить в графическом режиме соответствующие гистограммы сравнений и перестановок, а также времени работы.
Для изучения эффективности работы, каждой сортировкой по очереди сортируются три вида массивов:
1. Отсортированный в прямом порядке
2. Отсортированный в обратном порядке
3. Массив случайных чисел.
Сортировка проводится над массивами объёмом 100, 5000 и 30000 элементов .
2. Сортировка прямым выбором
2.1 Разработка алгоритма сортировки прямым выбором
Алгоритм сортировки прямым выбором в некотором смысле противоположен сортировке прямыми включениями.
При прямом включении на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готовой последовательности для нахождения места включения.
При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.
Метод сортировки прямым выбором основан на следующих правилах:
· Выбирается элемент с наименьшим ключом.
· Он меняется местами с первым элементом a0.
· Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.
Таблица 1
|
|
-0,11 |
0,27 |
0,48 |
0,05 |
-24 |
0,09 |
1,46 |
-0,39 |
-1,00 |
23 |
45 |
|
-24 |
|
0,27 |
0,48 |
0,05 |
0,57 |
0,09 |
1,46 |
-0,39 |
-1,00 |
23 |
45 |
|
-24 |
-1,00 |
|
0,48 |
0,05 |
0,57 |
0,09 |
1,46 |
-0,39 |
-0,11 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
|
0,05 |
0,57 |
0,09 |
1,46 |
0,27 |
-0,11 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
|
0,57 |
0,09 |
1,46 |
0,27 |
0,48 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
|
0,09 |
1,46 |
0,27 |
0,48 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
|
1,46 |
0,27 |
0,48 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
|
0,57 |
0,48 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
0,48 |
0,57 |
1,46 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
0,48 |
0,57 |
1,46 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
0,48 |
0,57 |
1,46 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
0,48 |
0,57 |
1,46 |
23 |
45 |
|
-24 |
-1,00 |
-0,39 |
-0,11 |
0,05 |
0,09 |
0,27 |
0,48 |
0,57 |
1,46 |
23 |
45 |
0,57
-0,11
0,27
0,48
0,05
0,57
0,57
1,462.2 Алгоритм сортировки прямым выбором
Блок-схема 1. Процедура сортировки массива методом прямого выбора.
2.3 Текст процедуры для сортировки прямым выбором
procedure FindMin(startindex:integer;M:ar;var lowindex: integer);{Перебирает массив начиная с заданного индекса и находим минимальный элемент}
var min,u:integer;
begin
lowindex:= startindex;
min := M[startindex];
for u:=startindex+1 to N-1 do
begin
inc(Psrav);
if M[u]< min then
begin
min := M[u];
lowindex:= u;
end;
end;
end;
…
procedureswap(varx,y,z: integer);{Меняем местами заданные элементы массива}
var t: integer;
begin
t := x;
x := y;
y := t;
inc(z);
end;
…
procedure Pryamoi_vibor(M:Ar);{Сортирует массив с помощью прямого выбора}
var
j:integer;
begin
for j:=0 to N-1 do
begin
FindMin(j,m,i);
swap(M[j],M[i],Pper);
end
end;
3. Шейкерная сортировка
3.1 Разработка алгоритма шейкерной сортировки
Шейкерная сортировка − разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу. Своим появлением эта сортировка обязан такому недостатку сортировки «пузырьком», при котором «лёгкие пузырьки» всплывают за один проход, а «тяжёлые» − тонут за несколько. Такая ассиметрия и вызвала появление новой сортировки, на каждом шаге которой осуществляется проход как в одну сторону, так и в другую. Таким образом, на каждом шаге «лёгкий пузырёк» всплывает на поверхность, а «тяжёлый» − тонет.
Метод этот получил название шейкерной сортировки.
Таблица 2
|
Шаг |
Направление движения |
Элементы массива |
||||||
|
55 |
18 |
70 |
10 |
17 |
75 |
68 |
||
|
1 |
Справа-налево |
10 |
55 |
18 |
70 |
17 |
68 |
75 |
|
Слева-направо |
10 || |
18 |
55 |
17 |
68 |
70 |
75 |
|
|
2 |
Справа-налево |
10 || |
17 |
18 |
55 |
68 |
70 |
|| 75 |
|
Слева-направо |
10 |
17 || |
18 |
55 |
68 |
70 |
|| 75 |
|
|
3 |
Справа-налево |
10 |
17 || |
18 |
55 |
68 |
|| 70 |
75 |
|
Слева-направо |
10 |
17 |
18 || |
55 |
68 |
|| 70 |
75 |
Серым цветом в таблице выделена та часть массива, которая исключается из просмотра.
3.2 Алгоритм шейкерной сортировки
Блок-схема 2. Процедура шейкерной сортировки массива.
3.3 Текст процедуры шейкернойсортировки
procedure Shaker(M:Ar);{Сортирует массив методом смешивания}
var
j,k,l,r:integer;
begin
L:=2;
R:=N-1;
k:=R;
Repeat
begin
for j:=r downto l-1 do
begin
if M[j-1] > M[j] then
begin
swap(M[j],M[j-1],Sper);
k:=j;
end;
inc(Ssrav);
end;
L:=k+1;
for j:=l to r do
begin
if M[j-1]> M[j] then
begin
swap(M[j],M[j-1],Sper);
k:=j;
end;
inc(Ssrav);
end;
r:=k-1;
end;
until L>R;
end;
4. Быстрая сортировка
4.1 Разработка алгоритма быстрой сортировки
Быстрая сортировка, часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов). Этот улучшенный метод сортировки основан на обмене.
Если количество элементов в массиве не многим меньше максимального их значения, то в данном случае наиболее эффективным и по быстродействию, и по простоте является быстрая сортировка. Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), в среднем требует только около N log N операций для того, чтобы отсортировать N элементов, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.Основная идея алгоритма быстрой сортировки состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x.
Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследить этот процесс можно на примере таблицы (таблица 2).
Таблица 3
|
Начальное состояние массива |
8 23 5 65 44 33 1 6 |
|
Шаг 1. (в качестве x выбирается a[4]) |
8 23 5 65 44 33 1 6 |-------------| 8 23 5 6 44 33 1 65 |
|
Шаг 2. (в подмассиве a[1..7] за x выбирается a[4]) |
8 23 5 6 44 33 1 65 |-------------------| 1 23 5 6 44 33 8 65 |-----| 1 6 5 23 44 33 8 65 |
|
Шаг 3. (в подмассиве a[1..3] в качестве x выбирается a[2]) |
1 6 5 23 44 33 8 65 |--| 1 5 6 23 44 33 8 65 |
|
Шаг 4. (в подмассиве a[4..7] в качестве x выбирается a[5]) |
1 5 6 23 44 33 8 65 |-----| 1 5 6 23 8 33 44 65 |
|
Шаг 5. (в подмассиве a[4..6] в качестве x выбирается a[5]) |
1 5 6 23 8 33 44 65 |---| 1 5 6 8 23 33 44 65 |
4.2 Алгоритм быстрой сортировки массива.
Блок-схема 3. Процедура быстрой сортировки массива
4.3 Текст процедуры быстрой сортировки
procedure Qsort(l,r:integer);{Сортирует массив Быстрой сортировкой}
var i,j,w:integer;
begin
i := l; j := r;
w := Q[(l+r) div 2];
repeat
while (Q[i] < w) do begin inc(i); inc(Qsrav); end;
while (w < Q[j]) do begin dec(j); inc(Qsrav); end;
if (i <= j) then
begin
swap(Q[i],Q[j],Qper);
inc(i); dec(j);
end;
until (i > j);
if (l < j) then qSort(l,j);
if (i < r) then qSort(i,r);
end;
5. Графическая работа
Для того, чтобы изобразить гистограммы и таблицы по полученным данным, воспользуемся процедурами из модулей GraphABC и ABCobjects.
Готовый алгоритм построения гистограмм для значений из массива Q выглядит следующим образом:
Procedure Gist;{Строит гистрограмму одного массива}
var
a,c,b:integer;
x:real;
begin
SetBrushColor(clgreen);
Textout(500,5,"Быстрая");
SetBrushColor(clDarkOrchid);
Textout(600,5,"Прямая");
SetBrushColor(clHotPink);
Textout(700,5,"Шейкерная");
SetBrushColor(clmoneygreen);
Textout(95,a+55,"Перемещений");
Textout(355,a+55,"Сравнений");
Textout(605,a+55,"Время в мсек.");
x:=Qper;
If x
If x
a:=round(90/(x/Qper));
b:=round(90/(x/Pper));
c:=round(90/(x/Sper));
SetBrushColor(clgreen);
FillRectangle(10,y+165,70,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(100,y+165,160,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(190,y+165,250,y+165-c+2);
x:=Qsrav;
If x
If x
a:=round(90/(x/Qsrav));
b:=round(90/(x/Psrav));
c:=round(90/(x/Ssrav));
SetBrushColor(clgreen);
FillRectangle(280,y+165,340,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(370,y+165,430,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(460,y+165,520,y+165-c+2);
x:=Qtime;
If x
If x
a:=round(90/(x/Qtime));
b:=round(90/(x/Ptime));
c:=round(90/(x/Stime));
SetBrushColor(clgreen);
FillRectangle(550,y+165,610,y+165-a+2);
SetBrushColor(clDarkOrchid);
FillRectangle(640,y+165,700,y+165-b+2);
SetBrushColor(clHotPink);
FillRectangle(730,y+165,790,y+165-c+2);
setpencolor(clblack);
SetBrushColor(clmoneygreen);
Textout(10,y+185,inttostr(Qper));
Textout(100,y+185,inttostr(Pper));
Textout(190,y+185,inttostr(Sper));
Textout(280,y+185,inttostr(Qsrav));
Textout(370,y+185,inttostr(Psrav));
Textout(460,y+185,inttostr(Ssrav));
str(Qtime:8:4,Qtimest);
str(Ptime:8:4,Ptimest);
str(Stime:8:4,Stimest);
Textout(550,y+185,Qtimest);
Textout(640,y+185,Ptimest);
Textout(730,y+185,Stimest);
end;
6. Расчёт времени выполнения сортировки
Для расчета времени выполнения сортировки воспользуемся встроенным модулем Timers.
Так как модуль Timers ограничен минимальным значением в 1 мс., а сортировка массива из 100 значений на современном компьютере выполняется значительно быстрее, то мы выполним сортировку n раз а потом разделим значение таймера на n, чтобы получить среднее время выполнения сортировки.
Создадим свой экземпляр таймера для каждого типа сортировки.
Готовый пример обработчика модуля Timers:
Procedure Qtimer;
begin
Qtime:=Qtime+1;
end;
Procedure Stimer;
begin
Stime:=Stime+1;
end;
Procedure Ptimer;
begin
Ptime:=Ptime+1;
end;
Замерять время будем в процедуре запуска сортировок:
Procedure Zapusk(N:integer);{Организует построение массивов и их сортировкуи вывод с помощью процедур}
var i:integer;
var qt:=new Timer(1,Qtimer);
var pt:=new Timer(1,Ptimer);
var st:=new Timer(1,Stimer);
begin
SetLength(Order,N);
SetLength(Reverse,N);
SetLength(Arandom,N);
Buildar;
Qtime:=0;
qt.start;
if N=30000 then
begin
for i:=1 to 10 do
begin
Q:=Copy(Arandom);
Qsort(0,N-1);
end;
qt.stop;
Qtime:=Qtime/10;
Qsrav:=round(Qsrav/10);
Qper:=round(Qper/10);
end
else
begin
for i:=1 to 2000 do
begin
Q:=Copy(Arandom);
Qsort(0,N-1);
end;
qt.stop;
Qtime:=Qtime/2000;
Qsrav:=round(Qsrav/2000);
Qper:=round(Qper/2000);
end;
Ptime:=0;
Q:=Copy(Arandom);
pt.start;
if N=100 then
begin
for i:=1 to 1000 do
begin
Q:=Copy(Arandom);
Pryamoi_vibor(Q);
end;
pt.stop;
Ptime:=Ptime/1000;
Psrav:=round(Psrav/1000);
Pper:=round(Pper/1000);
end
else
Pryamoi_vibor(Q);
pt.stop;
Stime:=0;
Q:=Copy(Arandom);
st.start;
if N=100 then
begin
for i:=1 to 2000 do
begin
Q:=Copy(Arandom);
Shaker(Q);
end;
st.stop;
Stime:=Stime/2000;
Ssrav:=round(Ssrav/2000);
Sper:=round(Sper/2000);
end
else
Shaker(Q);
st.stop;
…
end;
7. Обоснование технических приемов программирования
Для разработки программы анализа сортировок выбран Паскаль АБС как современная. гибкая платформа для языка высокого уровня. Которая, к тому же имеет встроенные процедуры для графического режима и замера времени.
Этапы выполнения программы:
1. Создание массивов размера N.
Так как мы используем динамические массивы, размер массива мы можем менять по ходу выполнения программы. Поэтому достаточно создать три массива Arandom, Order и Revers. по умолчанию N=100, так как это размерность массива сортирующаяся по умолчанию.
2. Заполнения массивов значениями.
Для заполнения массивов воспользуемся процедурой:
procedure BuildAr;{Заполняет 3 массива с заданными условиями}
var
i: integer;
begin
for i := 0 to N - 1 do
begin
Order[i] := i;
Revers[i] := N - i;
Arandom[i] := Random(N);
end;
end;
3. Сортировка массива
Создаем копию массива для каждой сортировки , чтобы сортировались полностью одинаковые массивы. Во время выполнения сортировки замеряем количество перестановок и сравнений. Так как массивы в 100 значений сортируются очень быстро, и мы не успеваем замерить их с помощью встроенного таймера – Выполняем сортировку маленьких массивов S раз. А после результат делим на S. Так мы получаем усредненное время выполнения сортировки. S выбирается для каждой сортировки отдельно, для достижения правильного результата.
4.Вывод результатов
В программе имеется шесть окон для вывода результатов. Они закреплены за кнопками на цифровой клавиатуре. Три окна для вывода результата в виде таблицы (для каждого размера массива), и соответственно три окна для вывода в виде гистограмм.
Для вывода таблиц и гистограмм используются отдельные процедуры, для выбора нужно используется переменная Gist.
По умолчанию выводится результат сортировок массива размером в 100 элементов.
При переключении окна последовательно выполняется: заполнение массивов размера N. сортировки массивов, вывод на экран в заданном режиме.
То есть сортировка каждого размера выполняется отдельно, это сделано, для ускорения выполнения программы, так как сортировка массива в 30000 значений может занять длительное время.
8. Системные требования
Системные требования для использования программы минимальны, так как не требуется выполнять объёмные вычисления.
Минимальные системные требования:
Процессор: Pentium 200 MHz
Оперативная память: 32 MB
Операционные системы: MS Windows 95
Монитор с поддержкой графического режима разрешением 640 x 480
Клавиатура
Мышь
9. Инструкции пользователю
Интерфейс программы выполнен на русском языке и позволяет запустить программу и произвести сортировку. От пользователя требуется лишь следовать инструкциям.
Программа работает в двух основных режимах: текстовом и графическом.
В текстовом режиме пользователю доступны 3 таблицы с данными: для массивов из 100, 5000 и 30000 элементов.
Рисунок 1. Пример работы программы в текстовом режиме
В графическом режиме пользователю доступны 3 экрана с тремя гистограммами на каждом: для массивов из 100, 5000 и 30000 элементов.
Рисунок 2. Пример работы программы в графическом режиме
Для управления программой предусмотрены следующие горячие клавиши:
1 – Отображение данных для массива из 100 элементов в виде таблицы
2 – Отображение данных для массива из 5000 элементов в виде таблицы
3 – Отображение данных для массива из 30000 элементов в виде таблицы
4 – Отображение данных для массива из 100 элементов в виде гистограмм
5– Отображение данных для массива из 5000 элементов в виде гистограмм
6 – Отображение данных для массива из 30000 элементов в виде гистограмм
7 – Выход из программы
10. Тестирование программы
Программа тестировалась на компьютере с процессором AMD 2800 GHz и 8 GВ RAM. Работающим по Win 7 Service pack 1. При установленных PascalABC.NET (версия 3.1, сборка 1250) и Microsoft .NET Framework v4.0
В ходе тестирования никаких особенностей не выявлено.
8. Анализ полученных результатов
Анализ сортировки двоичным включением.
Число сравнений при использовании данного метода фактически не зависит от начального порядка элементов.
Для С имеем С = (n2 - n)/2
Число перестановок минимально Mmin=3*(n-l ) в случае изначально упорядоченных ключей, и максимально Mmax = n2/4 +3(n-1) для обратного порядка ключей.
Анализ шейкерной сортировки.
Минимальное
число сравнений равно 
= (n – 1)
Максимальное
число сравнений равно 
= (
− n) / 2
Максимальное
число пересылок 
= 3( − n) / 2
Число же перестановок не меняется в сравнении с методом «пузырька», поэтому скорость работы алгоритма возрастает незначительно. Лучший случай для этой сортировки - отсортированный массив (О(n)), худший - отсортированный в обратном порядке (O(n²)).
Анализ быстрой сортировки.
Для оценок сложности усовершенствованных методов сортировки точных формул нет. Процесс разделения идет следующим образом: выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. При этом выполняется точно n сравнений. Ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.
M = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n =
= [Su:0 <= u <= n-1: u*(n-u)]/n2 =
= n*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 (7)
В том случае, если бы всегда удавалось выбирать в качестве границы медиану, то каждый процесс разделения расщеплял бы массив на две половинки, и для сортировки требовалось бы всего n*log n подходов. В результате общее число сравнений и обменов было бы соответственно
Cmax = n*log n,
Mmax = n*log(n) /6.
Но вероятность этого составляет только 1/n.
Главный из недостатков Quicksort – недостаточно высокая производительность при небольших n, впрочем этим грешат все усовершенствованные методы, одним из достоинств является то, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки.
После выполнения программы мы получили следующие сведения, которые можно наблюдать в таблицах и гистограммах на нижеприведённых рисунках.
Рисунок 3. Данные сортировки массивов из 100 элементов.
Рисунок 4. Гистограммы сортировки массивов из 100 элементов.
Рисунок 5. Данные сортировки массивов из 5000 элементов.
Рисунок 6. Гистограммы сортировки массивов из 5000 элементов.
Рисунок 7. Данные сортировки массивов из 30000 элементов.
Рисунок 8. Гистограммы сортировки массивов из 30000 элементов.
Изучив полученные результаты и сравнив их с известными формулами, мы получили следующую таблицу максимальных значений.
Таблица 4. Сравнение максимальных теоретических и
практических результатов сортировок массивов.
|
100 |
5000 |
30000 |
||
|
Прямой выбор |
перестановки |
---------- 100 |
---------- 5100 |
--------- 30100 |
|
сравнения |
4950 4950 |
12502450 12502450 |
299774746 299774746 |
|
|
время |
--------------- 0.003 |
--------------- 5 |
--------------- 222 |
|
|
Шейкерная сортировка |
перестановки |
14850 4950 |
37507350 12497500 |
899324238 449985000 |
|
сравнения |
4950 4999 |
12502450 12499999 |
299774746 449999999 |
|
|
время |
--------------- 0.0085 |
--------------- 20 |
--------------- 724 |
|
|
Быстрая сортировка |
перестановки |
33 192 |
224 16203 |
500 114465 |
|
сравнения |
200 442 |
1349 44708 |
3000 353195 |
|
|
время |
--------------- 0.0015 |
--------------- 0.0825 |
--------------- 0.6 |
* - в числителе дано теоретическое значение, в знаменателе – практическое значение в результате выполнения программы
Заключение
Из выполненного анализа очевидно, что шейкерная сортировка чаще всего оказывается самой ресурсоемкой, например при сортировке массива из 5000 элементов, отсортированного в обратном порядке, максимально возможное число пересылок равно 12497500.
Лучшим из трёх методов по ресурсоемкости является метод быстрой сортировки, но только для больших массивов.
Из полученных гистограмм хорошо видно какой вид сортировки выполняется быстрее. Причем, если для массива из 100 элементов разница невелика, то с увеличением размера массива, разница становится очевидна.
Как видно,метод быстрой сортировки − самый быстрый вид сортировки, потому что во всех случаях он показывал наименьшее время.
Самый же медленный метод сортировки – шейкерная сортировка.
По сравнению с методом быстрой сортировкидля массива из 1000 элементов он медленнее почти в 60 раз.
После исследования трёх видов сортировок, самым эффективным по всем оцениваемым параметрам оказался метод быстрой сортировки (не зря он получил такое название quick – быстрый).
Литература
1. http://en.wikipedia.org/wiki/Cocktail_sort
http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort
http://ru.wikipedia.org/wiki/Быстрая_сортировка
http://ru.wikipedia.org/wiki/Шейкерная_сортировка
2. Вирт Н. Алгоритмы и структуры данных / Пер. с англ. Д.Б. Подшивалова. – М.: Мир, 1989. - 360 с.: ил.
3. Глухова Л.А. Основы алгоритмизации и программирования: Лаб. практикум для студ. спец. I-40 01 01 «Программное обеспечение информационных технологий» дневной формы обуч. В 4 ч. Ч. 2 / Л.А. Глухова, Е.П. Фадеева, Е.Е. Фадеева. – Мн.: БГУИР, 2005. – 52 с.
4. ГОСТ 19.701-90 (ИСО 5807-85). Единая система программной документации. Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения. – М.: Гос. комитет СССР по управлению качеством продукции и стандартам, 1991. – 26
5. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль / Пер. с англ.; Предисл. Ю.П.Широкого. – М.: Финансы и статистика, 1991. – 720 с.: ил.
6. Климов Ю.С. и др. Программирование в среде Turbo Pascal 6.0: Справ. пособие / Ю.С.Климов, А.И.Касаткин, С.М.Мороз. – Мн.: Выш. шк., 1992. – 158 с.: ил.
7. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск / Knuth Donald. The Art of Computer Programming. Vol.3. Sorting and Searching. − 2-е изд. − М.: Вильямс, 2007. − 824 c. − ISBN 0-201-89685-0
8. Кузнецов С.Д. Методы сортировки и поиска (http://www.citforum.ru/programming/theory/sorting.shtml).
9. Офицеров Д.В., Старых В.А. Программирование в интегрированной среде Турбо-Паскаль: Справ. пособие. - Мн.: Беларусь, 1992. - 240с.: ил.
10. Фаронов В.В. Turbo Pascal. – СПб.: БХВ-Петербург, 2006. – 1056 с.: ил.
11. Энциклопедия Turbo Pascal. (http://www.cyberguru.ru/programming/pascal/turbopascal-encyclopaedia.html)
Приложение А
Текст программы для сортировки массивов
program Analiz_sortirovok;{Программа выполняет сортировку массивов разными способами}
uses GraphAbc,timers,ABCobjects;
type
Ar = array of integer;
var
Order, Revers, Arandom, Q: Ar;
Qsrav, Ssrav, Psrav, Qper, Pper, Sper, N, y, i: integer;
Qtimest, Stimest, Ptimest: string;
Qtime, Stime, Ptime: real;
gisto: boolean;
procedure BuildAr;{Заполняет 3 массива с заданными условиями}
var
i: integer;
begin
for i := 0 to N - 1 do
begin
Order[i] := i;
Revers[i] := N - i;
Arandom[i] := Random(N);
end;
end;
procedure swap(var x, y, z: integer);{Меняем местами заданные элементы массива}
var
t: integer;
begin
t := x;
x := y;
y := t;
inc(z);
end;
procedure FindMin(startindex: integer; M: ar; var lowindex: integer);{Перебирает массив начиная с заданного индекса и находим минимальный элемент}
var
min, u: integer;
begin
lowindex := startindex;
min := M[startindex];
for u := startindex + 1 to N - 1 do
begin
inc(Psrav);
if M[u] < min then
begin
min := M[u];
lowindex := u;
end;
end;
end;
procedure Pryamoi_vibor(M: Ar);{Сортирует массив с помощью прямого выбора}
var
j: integer;
begin
for j := 0 to N - 1 do
begin
FindMin(j, m, i);
swap(M[j], M[i], Pper);
end
end;
procedure Shaker(M: Ar);{Сортирует массив методом смешивания}
var
j, k, l, r: integer;
begin
L := 2;
R := N - 1;
k := R;
repeat
begin
for j := r downto l - 1 do
begin
if M[j - 1] > M[j] then
begin
swap(M[j], M[j - 1], Sper);
k := j;
end;
inc(Ssrav);
end;
L := k + 1;
for j := l to r do
begin
if M[j - 1] > M[j] then
begin
swap(M[j], M[j - 1], Sper);
k := j;
end;
inc(Ssrav);
end;
r := k - 1;
end;
until L > R;
end;
procedure Qsort(l, r: integer);{Сортирует массив Быстрой сортировкой}
var
i, j, w: integer;
begin
i := l; j := r;
w := Q[(l + r) div 2];
repeat
while (Q[i] < w) do begin inc(i); inc(Qsrav); end;
while (w < Q[j]) do begin dec(j); inc(Qsrav); end;
if (i <= j) then
begin
swap(Q[i], Q[j], Qper);
inc(i); dec(j);
end;
until (i > j);
if (l < j) then qSort(l, j);
if (i < r) then qSort(i, r);
end;
procedure Qtimer;{засекает время выполнения быстрой сортировки}
begin
Qtime := Qtime + 1;
end;
procedure Stimer;{засекает время выполнения шейкерной сортировки}
begin
Stime := Stime + 1;
end;
procedure Ptimer;{засекает время выполнения сортировки прямым выбором}
begin
Ptime := Ptime + 1;
end;
procedure Gist;{Строит гистрограмму одного массива}
var
a, c, b: integer;
x: real;
begin
SetBrushColor(clgreen);
Textout(500, 5, "Быстрая");
SetBrushColor(clDarkOrchid);
Textout(600, 5, "Прямая");
SetBrushColor(clHotPink);
Textout(700, 5, "Шейкерная");
SetBrushColor(clmoneygreen);
Textout(95, a + 55, "Перемещений");
Textout(355, a + 55, "Сравнений");
Textout(605, a + 55, "Время в мсек.");
x := Qper;
if x < Pper then x := Pper;
if x < Sper then x := Sper;
a := round(90 / (x / Qper));
b := round(90 / (x / Pper));
c := round(90 / (x / Sper));
SetBrushColor(clgreen);
FillRectangle(10, y + 165, 70, y + 165 - a + 2);
SetBrushColor(clDarkOrchid);
FillRectangle(100, y + 165, 160, y + 165 - b + 2);
SetBrushColor(clHotPink);
FillRectangle(190, y + 165, 250, y + 165 - c + 2);
x := Qsrav;
if x < Psrav then x := Psrav;
if x < Ssrav then x := Ssrav;
a := round(90 / (x / Qsrav));
b := round(90 / (x / Psrav));
c := round(90 / (x / Ssrav));
SetBrushColor(clgreen);
FillRectangle(280, y + 165, 340, y + 165 - a + 2);
SetBrushColor(clDarkOrchid);
FillRectangle(370, y + 165, 430, y + 165 - b + 2);
SetBrushColor(clHotPink);
FillRectangle(460, y + 165, 520, y + 165 - c + 2);
x := Qtime;
if x < Ptime then x := Ptime;
if x < Stime then x := Stime;
a := round(90 / (x / Qtime));
b := round(90 / (x / Ptime));
c := round(90 / (x / Stime));
SetBrushColor(clgreen);
FillRectangle(550, y + 165, 610, y + 165 - a + 2);
SetBrushColor(clDarkOrchid);
FillRectangle(640, y + 165, 700, y + 165 - b + 2);
SetBrushColor(clHotPink);
FillRectangle(730, y + 165, 790, y + 165 - c + 2);
setpencolor(clblack);
SetBrushColor(clmoneygreen);
Textout(10, y + 185, inttostr(Qper));
Textout(100, y + 185, inttostr(Pper));
Textout(190, y + 185, inttostr(Sper));
Textout(280, y + 185, inttostr(Qsrav));
Textout(370, y + 185, inttostr(Psrav));
Textout(460, y + 185, inttostr(Ssrav));
str(Qtime:8:4, Qtimest);
str(Ptime:8:4, Ptimest);
str(Stime:8:4, Stimest);
Textout(550, y + 185, Qtimest);
Textout(640, y + 185, Ptimest);
Textout(730, y + 185, Stimest);
end;
procedure Tabl;{Строит таблицу одного массива}
begin
SetPenWidth(3);
SetPenColor(clblack);
Line(2, y + 50, 788, y + 50);
Line(2, y + 170, 788, y + 170);
Line(2, y + 50, 2, y + 170);
Line(788, y + 50, 788, y + 170);
Line(195, y + 50, 195, y + 170);
Line(395, y + 50, 395, y + 170);
Line(595, y + 50, 595, y + 170);
Line(2, y + 85, 788, y + 85);
Line(2, y + 115, 788, y + 115);
Line(2, y + 145, 788, y + 145);
Textout(5, y + 60, " Значения");
Textout(205, y + 60, "Быстрая сортировка");
Textout(405, y + 60, "Прямая сортировка");
Textout(605, y + 60, "Шейкерная сортировка");
Textout(5, y + 90, " Перемещений");
Textout(205, y + 90, inttostr(Qper));
Textout(405, y + 90, inttostr(Pper));
Textout(605, y + 90, inttostr(Sper));
Textout(5, y + 120, " Сравнений");
Textout(205, y + 120, inttostr(Qsrav));
Textout(405, y + 120, inttostr(Psrav));
Textout(605, y + 120, inttostr(Ssrav));
str(Qtime:8:4, Qtimest);
str(Ptime:8:4, Ptimest);
str(Stime:8:4, Stimest);
Textout(5, y + 150, " Время в мсек");
Textout(205, y + 150, Qtimest);
Textout(405, y + 150, Ptimest);
Textout(605, y + 150, Stimest);
end;
procedure Result(l: integer);{Организует построение массивов и их сортировку и вывод с помощью процедур}
var
i: integer;
var
qt := new Timer(1, Qtimer);
var
pt := new Timer(1, Ptimer);
var
st := new Timer(1, Stimer);
begin
N := l;
Textout(5, y, "Итоги сортировки массива в");
Textout(220, y, inttostr(l));
Textout(265, y, " значений");
SetLength(Order, l);
SetLength(Revers, l);
SetLength(Arandom, l);
Buildar;
Qtime := 0;
qt.start;
if l = 30000 then
begin
for i := 1 to 10 do
begin
Q := Copy(Arandom);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 10;
Qsrav := round(Qsrav / 10);
Qper := round(Qper / 10);
end
else
begin
for i := 1 to 2000 do
begin
Q := Copy(Arandom);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 2000;
Qsrav := round(Qsrav / 2000);
Qper := round(Qper / 2000);
end;
Ptime := 0;
Q := Copy(Arandom);
pt.start;
if l = 100 then
begin
for i := 1 to 1000 do
begin
Q := Copy(Arandom);
Pryamoi_vibor(Q);
end;
pt.stop;
Ptime := Ptime / 1000;
Psrav := round(Psrav / 1000);
Pper := round(Pper / 1000);
end
else
Pryamoi_vibor(Q);
pt.stop;
Stime := 0;
Q := Copy(Arandom);
st.start;
if l = 100 then
begin
for i := 1 to 2000 do
begin
Q := Copy(Arandom);
Shaker(Q);
end;
st.stop;
Stime := Stime / 2000;
Ssrav := round(Ssrav / 2000);
Sper := round(Sper / 2000);
end
else
Shaker(Q);
st.stop;
Textout(5, 30, "Случайно заполненный массив");
if gisto = false then
Tabl
else
Gist;
y := y + 180;
Qsrav := 0;
Qper := 0;
Ssrav := 0;
Sper := 0;
Psrav := 0;
Pper := 0;
Qtime := 0;
qt.start;
if l = 30000 then
begin
for i := 1 to 10 do
begin
Q := Copy(Revers);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 10;
Qsrav := round(Qsrav / 10);
Qper := round(Qper / 10);
end
else
begin
for i := 1 to 2000 do
begin
Q := Copy(Revers);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 2000;
Qsrav := round(Qsrav / 2000);
Qper := round(Qper / 2000);
end;
Ptime := 0;
Q := Copy(Revers);
pt.start;
if l = 100 then
begin
for i := 1 to 1000 do
begin
Q := Copy(Revers);
Pryamoi_vibor(Q);
end;
pt.stop;
Ptime := Ptime / 1000;
Psrav := round(Psrav / 1000);
Pper := round(Pper / 1000);
end
else
Pryamoi_vibor(Q);
pt.stop;
Stime := 0;
Q := Copy(Revers);
st.start;
if l = 100 then
begin
for i := 1 to 2000 do
begin
Q := Copy(Revers);
Shaker(Q);
end;
st.stop;
Stime := Stime / 2000;
Ssrav := round(Ssrav / 2000);
Sper := round(Sper / 2000);
end
else
Shaker(Q);
st.stop;
Textout(5, 215, "Обратно упорядоченный массив");
if gisto = false then
Tabl
else
Gist;
y := y + 180;
Qsrav := 0;
Qper := 0;
Ssrav := 0;
Sper := 0;
Psrav := 0;
Pper := 0;
Qtime := 0;
qt.start;
if l = 30000 then
begin
for i := 1 to 10 do
begin
Q := Copy(Order);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 10;
Qsrav := round(Qsrav / 10);
Qper := round(Qper / 10);
end
else
begin
for i := 1 to 2000 do
begin
Q := Copy(Order);
Qsort(0, l - 1);
end;
qt.stop;
Qtime := Qtime / 2000;
Qsrav := round(Qsrav / 2000);
Qper := round(Qper / 2000);
end;
Ptime := 0;
Q := Copy(Order);
pt.start;
if l = 100 then
begin
for i := 1 to 1000 do
begin
Q := Copy(Order);
Pryamoi_vibor(Q);
end;
pt.stop;
Ptime := Ptime / 1000;
Psrav := round(Psrav / 1000);
Pper := round(Pper / 1000);
end
else
Pryamoi_vibor(Q);
pt.stop;
Stime := 0;
Q := Copy(Order);
st.start;
for i := 1 to 10000 do
begin
Q := Copy(Order);
Shaker(Q);
end;
st.stop;
Stime := Stime / 10000;
Ssrav := round(Ssrav / 10000);
Sper := round(Sper / 10000);
Textout(5, 395, "Упорядоченный массив");
if gisto = false then
Tabl
else
Gist;
end;
procedure menu(key: integer);{Обрабатывает команды с клавиатуры}
begin
case Key of
97: begin Clearwindow(clmoneygreen); y := 5; gisto := false; Result(100); end;
98: begin Clearwindow(clmoneygreen); y := 5; gisto := false; Result(5000); end;
99: begin Clearwindow(clmoneygreen); y := 5; gisto := false; Result(30000); end;
100: begin Clearwindow(clmoneygreen); y := 5; gisto := true; Result(100); end;
101: begin Clearwindow(clmoneygreen); y := 5; gisto := true; Result(5000); end;
102: begin Clearwindow(clmoneygreen); y := 5; gisto := true; Result(30000); end;
103: Closewindow;
end;
end;
procedure initialize;{Инициализирует графическое окно, и выполняет начальную настройку}
begin
y := 5;
gisto := false;
SetWindowSize(800, 600);
CenterWindow;
SetbrushColor(clmoneygreen);
FillroundRect(0, 0, 800, 600, 1, 3);
SetWindowCaption("Анализ сортировок");
SetpenColor(clBlack);
SetpenWidth(2);
setfontsize(12);
onkeydown := menu;
end;
begin
initialize;
Result(100);
end.
(zip - application/zip)
Статистика файлового архива
