3.4.Реализация замера времени выполнения алгоритмов сортировки в программе

Помимо подсчетов кол-ва сравнений, присваиваний и эффективности, в программе предусмотрен замер времени выполнения алгоритмов с многократным повторением. Для его реализации фиксируется начальное время перед началом алгоритма и после его выполнения с помощью функции gettime(), которая возвращает структуру с заполненными полями текущего времени и даты. Далее, разницу во времени с помощью формулы из миллисекунд преобразуем в секунды. Начальное и конечное время фиксируется до и после алгоритма сортировки, который, в свою очередь, повторяется определенное пользователем кол-во раз (по умолчанию 1000000).

Таким образом, фрагмент кода подсчета времени может выглядеть так:

struct time t1,t2; // структура для замера времени выполнения сортировки

gettime(&t1); // фиксируем начальное время сортировки

for (c = 0; c < SortCount; c++) { // цикл прохождения сортировок SortCount раз

for (i = 0; i < arSize; i++)

arRes[i] = arSource [i]; // скопируем содержимое исх.массива в

// массив с результатом

QuickSort(arRes, arSize - 1); // отсортируем массив с результатом

}

gettime(&t2); // фиксируем конечное время сортировки

// формула перевода в секунды

t_sort = (t2.ti_hour*360000.+t2.ti_min*6000.+ t2.ti_sec*100.+t2.ti_hund-(t1.ti_hour*360000.+ t1.ti_min*6000.+t1.ti_sec*100.+t1.ti_hund))/100.;

// для достоверности результатов, вычтем из результата время, потраченное на копирование из массива в массив перед каждой новой сортировкой

t_sort = t_sort - t_copy;

Здесь t_copy – заранее определенная переменная, которая хранит время выполнения копирования из одного массива в другой SortCount раз

Так как в подсчете эффективности в курсовом проекте предусмотрены как замер времени выполнения так и подсчет кол-ва сравнений и присваиваний, то для того, чтобы подсчет времени был справедливым (без учета операций суммирования счетчиков присваиваний и сравнений) в курсовом проекте было для каждого из двух методов определения эффективности реализованы по два дубля алгоритма сортировки. В первом ведется подсчет кол-ва сравнений и присваиваний, а во втором подряд идущем коде замеряется время выполнения.

3.5.Реализация представления результата в программе

Для анализа результатов работы алгоритмов сортировки в программе предусмотрено два способа представления:

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

   • Кол-во сравнений

   • Кол-во присваиваний

   • Условная эффективность

   • Время, затраченное на сортировку с кол-вом повторений сортировок, определенных пользователем

2. Графическое представление результатов сортировок по каждому методу сортировки с показом графика зависимости размерности массива от времени выполнения, а также вывод прямолинейных диаграмм по каждой размерности. Отображение графика и диаграмм меняется в зависимости от выбранного способа заполнения исходных массивов (убывающий порядок – для худшего случая сортировки и случайный порядок). Вся информация в графическом представлении базируется на основе времени выполнения алгоритмов. (Сравнения, присваивания и эффективность на графиках не приводятся, т.к. показания фактического вермени выполнения алгоритмом более актуальна).

Результат оценки производительности алгоритмов поиска представлен в виде двух характеристик – кол-во сравнения и кол-во итераций.