Аналитический обзор существующих аналогов

Стр 1 из 4Следующая ⇒

Содержание.

Введение 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

ВВЕДЕНИЕ

Сортировка – это процесс упорядочения множества подобных информационных объектов в некотором определённом порядке с целью облегчения последующего поиска нужных элементов.

Под сортировкой в программировании чаще всего понимается такая перестановка предметов, при которой они располагаются в порядке возрастания или убывания.

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа чаще всего выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Прежде, чем изучать методы сортировки, следует ввести некоторые понятия и обозначения. Пусть имеются элементы

а₁, a₂, ……, а_n

то сортировка есть перестановка этих элементов в массив

а_k₁, a_k₂, ……, a_kn

где

a_k₁ < = a_k₂ < = ….. < = a_kn.

Каждый из алгоритмов сортировки имеет и свои достоинства, и свои недостатки, поэтому при сортировке выбирать алгоритм нужно, исходя из конкретной постановки задачи.

В качестве оценки методов сортировки удобно использовать понятие экономичности, т. е. время их работы. Мерой эффективности в данном случае служит:

C – число необходимых сравнений ключей и

M – число пересылок (перестановок) элементов.

Методы сортировки делятся на три типа:

1. методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;

2. методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;

3. и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.

Аналитический обзор существующих аналогов

В настоящее время существует множество алгоритмов сортировки массивов, которые применяются в зависимости от того какие условия функционирования стоят перед разрабатываемой программой.

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 элементов.

Сортировка прямым выбором

Разработка алгоритма сортировки прямым выбором

Алгоритм сортировки прямым выбором в некотором смысле противоположен сортировке прямыми включениями.

При прямом включении на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готовой последовательности для нахождения места включения.

При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.

Метод сортировки прямым выбором основан на следующих правилах:

· Выбирается элемент с наименьшим ключом.

· Он меняется местами с первым элементом a₀.

· Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

Таблица 1

0, 57	-0, 11	0, 27	0, 48	0, 05	-24	0, 09	1, 46	-0, 39	-1, 00
-24	-0, 11	0, 27	0, 48	0, 05	0, 57	0, 09	1, 46	-0, 39	-1, 00
-24	-1, 00	0, 27	0, 48	0, 05	0, 57	0, 09	1, 46	-0, 39	-0, 11
-24	-1, 00	-0, 39	0, 48	0, 05	0, 57	0, 09	1, 46	0, 27	-0, 11
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 57	0, 09	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 57	0, 09	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 57	1, 46	0, 27	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	1, 46	0, 57	0, 48
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46
-24	-1, 00	-0, 39	-0, 11	0, 05	0, 09	0, 27	0, 48	0, 57	1, 46

Алгоритм сортировки прямым выбором

Блок-схема 1. Процедура сортировки массива методом прямого выбора.

Прямой выбор

j, A, i

A[i], A[j]

Findmin

Swap

Input N, A[1..N]

j: =0 to N-1

Swap

Input i, j

t: =i

i: =j

j: =t

A[u]< min

Findmin

Input j, A, i

u: =j+1 to N-1

i: =j, min: =A[j]

min: =A[u]

i: =u

нет

да

Текст процедуры для сортировки прямым выбором

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;

…

procedure swap( var x, 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;

Шейкерная сортировка

Разработка алгоритма шейкерной сортировки

Шейкерная сортировка − разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу. Своим появлением эта сортировка обязан такому недостатку сортировки «пузырьком», при котором «лёгкие пузырьки» всплывают за один проход, а «тяжёлые» − тонут за несколько. Такая ассиметрия и вызвала появление новой сортировки, на каждом шаге которой осуществляется проход как в одну сторону, так и в другую. Таким образом, на каждом шаге «лёгкий пузырёк» всплывает на поверхность, а «тяжёлый» − тонет.

Метод этот получил название шейкерной сортировки.

Таблица 2

Шаг	Направление движения	Элементы массива

	Справа-налево
Слева-направо	10 \|\|
	Справа-налево	10 \|\|				\|\| 75
Слева-направо		17 \|\|			\|\| 75
	Справа-налево		17 \|\|		\|\| 70
Слева-направо			18 \|\|	\|\| 70

Серым цветом в таблице выделена та часть массива, которая исключается из просмотра.

Алгоритм шейкерной сортировки

Блок-схема 2. Процедура шейкерной сортировки массива.

l: =2; r: =N-1; k: =R

Input A[N]

Шейкер

A2 j: =r downto l-1

a[j-1] > a[j]

нет

да

A3 j: =l to r

A[j-1] > A[j]

нет

да

r: =k-1

A1 l> r

L: =k+1

A[j], A[j-1]

Swap

k: =j

A[j], A[j-1]

k: =j

Swap

Текст процедуры шейкерной сортировки

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;

Быстрая сортировка

Алгоритм быстрой сортировки массива.

Блок-схема 3. Процедура быстрой сортировки массива

QSort

i: =L, j: =R

A1i> j

Qsort

A[N], L, R

i < = j

w: =A[(L+R)div 2]

A2 A[i]< w

inc(i)

A3 w < A[j]

dec(j)

A[i], A[j]

inc(i), dec(j)

Swap

L < j

i < R

L, j

I, R

QSort

да

нет

да

Текст процедуры быстрой сортировки

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;

Графическая работа

Для того, чтобы изобразить гистограммы и таблицы по полученным данным, воспользуемся процедурами из модулей 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< 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;

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;

Var

i: integer;

Begin

for i: = 0 to N - 1 do

Begin

Order[i]: = i;

Revers[i]: = N - i;

Arandom[i]: = Random(N);

end;

3. Сортировка массива

Создаем копию массива для каждой сортировки, чтобы сортировались полностью одинаковые массивы. Во время выполнения сортировки замеряем количество перестановок и сравнений. Так как массивы в 100 значений сортируются очень быстро, и мы не успеваем замерить их с помощью встроенного таймера – Выполняем сортировку маленьких массивов S раз. А после результат делим на S. Так мы получаем усредненное время выполнения сортировки. S выбирается для каждой сортировки отдельно, для достижения правильного результата.

4.Вывод результатов

В программе имеется шесть окон для вывода результатов. Они закреплены за кнопками на цифровой клавиатуре. Три окна для вывода результата в виде таблицы (для каждого размера массива), и соответственно три окна для вывода в виде гистограмм.

Для вывода таблиц и гистограмм используются отдельные процедуры, для выбора нужно используется переменная Gist.

По умолчанию выводится результат сортировок массива размером в 100 элементов.

При переключении окна последовательно выполняется: заполнение массивов размера N. сортировки массивов, вывод на экран в заданном режиме.

То есть сортировка каждого размера выполняется отдельно, это сделано, для ускорения выполнения программы, так как сортировка массива в 30000 значений может занять длительное время.

8. Системные требования

Системные требования для использования программы минимальны, так как не требуется выполнять объёмные вычисления.

Минимальные системные требования:

Процессор: Pentium 200 MHz

Оперативная память: 32 MB

Операционные системы: MS Windows 95

Монитор с поддержкой графического режима разрешением 640 x 480

Клавиатура

Мышь

Инструкции пользователю

Интерфейс программы выполнен на русском языке и позволяет запустить программу и произвести сортировку. От пользователя требуется лишь следовать инструкциям.

Программа работает в двух основных режимах: текстовом и графическом.

В текстовом режиме пользователю доступны 3 таблицы с данными: для массивов из 100, 5000 и 30000 элементов.

Рисунок 1. Пример работы программы в текстовом режиме

В графическом режиме пользователю доступны 3 экрана с тремя гистограммами на каждом: для массивов из 100, 5000 и 30000 элементов.

Рисунок 2. Пример работы программы в графическом режиме

Для управления программой предусмотрены следующие горячие клавиши:

1 – Отображение данных для массива из 100 элементов в виде таблицы

2 – Отображение данных для массива из 5000 элементов в виде таблицы

3 – Отображение данных для массива из 30000 элементов в виде таблицы

4 – Отображение данных для массива из 100 элементов в виде гистограмм

5– Отображение данных для массива из 5000 элементов в виде гистограмм

6 – Отображение данных для массива из 30000 элементов в виде гистограмм

7 – Выход из программы

Тестирование программы

Программа тестировалась на компьютере с процессором AMD 2800 GHz и 8 GВ RAM. Работающим по Win 7 Service pack 1. При установленных PascalABC.NET (версия 3.1, сборка 1250) и Microsoft.NET Framework v4.0

В ходе тестирования никаких особенностей не выявлено.

Заключение

Из выполненного анализа очевидно, что шейкерная сортировка чаще всего оказывается самой ресурсоемкой, например при сортировке массива из 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)

Приложение А

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;

procedure swap( var x, y, z: integer); {Меняем местами заданные элементы массива}

Var

t: integer;

Begin

t: = x;

x: = y;

y: = t;

inc(z);

end;

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;

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;

12 3 4 Следующая ⇒