Расчёт времени выполнения сортировки

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

Обоснование технических приемов программирования

Для разработки программы анализа сортировок выбран Паскаль АБС как современная. гибкая платформа для языка высокого уровня. Которая, к тому же имеет встроенные процедуры для графического режима и замера времени.

Этапы выполнения программы:

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;

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

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

⇐ Предыдущая 1 234 Следующая ⇒