Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования ( Классы методов сортировки ).pdf

}

buf = array[k]; // перестановка минимума на позицию k

array[k] = array[j]; // ...................

array[j] = buf; // ...................

}

gettime( &t ); // получение системного времени

t2 = t.ti_hund; // запись сотых долей секунды

системного времени в переменную t2

ti = abs( t2 -t1 ); // вычисление времени выполнения цикла 1

return ti;

}

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

Функция sort будет не только сортировать массив, но и возвращать время сортировки в формате сотых долей секунды. Поэтому для проведения тестирования алгоритма далее в программе 2 с помощью функции main будем конкретизировать шаблон.

Программа 2.

#include <iostream.h>

#include <string.h>

#include <math.h>

int main()

{

// задание переменных для вычисления среднего времени

intinttime[15];

floatavtime = 0;

// задание размера сортируемого массива

constintsize = 100;

// заполнение массива целых чисел

int ia[size];

for(int x = 0; x < size; ++x ){

randomize();

ia[x] = random( 100 );

}

// конкретизация шаблона для массива типа int

cout << "sort time for ia[" << size << "] { ";

for(int x = 0; x < 15; ++x ){

inttime[x] = sort( ia );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

float fa[size];

for(int x = 0; x < size; ++x ){

randomize();

fa[x] = log( random( 100 ) + 1 );

}

// конкретизация шаблона для массива типа float

avtime = 0;

cout << "sort time for fa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( fa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

char ca[size];

for (int x = 0; x < size; ++x ){

randomize();

ca[x] = random( 64 ) + 62;

}

// конкретизация шаблона для массива типа char

avtime = 0;

cout << "sort time for ca[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( ca );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

string sa[size];

string samp = "deathisjustanotherpathonethatweallhavetotake";

int bag, fag;

string dag = "int";

for ( int x = 0; x < size; ++x ) {

bag = random( 44 );

fag = random( 44 );

sa[x] = dag + samp[bag] + samp[fag];

}

// конкретизация шаблона для массива типа string

avtime = 0;

cout << "sort time for sa[" << size << "] { ";

for (int x = 0; x < 15; ++x ){

inttime[x] = sort( sa );

cout << inttime[x] << " ";

avtime = avtime + inttime[x];

}

cout << "} average time: " << avtime/15 << endl;

cin.get();

return 0;

}

//---------------------------------------------------------------------------

2.3 Тестирование алгоритма

В данном разделе приступим к тестированию алгоритма. Для этого вновь обратимся к уже полученным формулам скорости выполнения алгоритма и попытаемся сопоставить полученные путем эксперимента данные с теоретическим обоснованием нашего алгоритма.

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

Путем варьирования константы size будем получать различные значения функции sort. Определив константу size значение 100, получим выведенное на консоль среднее из пятнадцати значений время сортировки для массивов различного типа (рис 4).

Рис.4. Консоль вывода времени сортировки

Как видно 100 это слишком малое количество записей в массиве, поэтому в дальнейшем будем увеличивать это значение, начиная с 0 с шагом в 500. Запуская программу для каждого размера массива и выбирая среднее из полученных значений времени, получили следующую таблицу данных.

Таблица 1

Время сортировки массива

На основании данной таблицы можно вывести закономерности и составить график зависимость времени сортировки массива от размера этого массива для четырех типов данных (рис 4).

Рис.5. График зависимости времени сортировки от числа элементов

3 Итоги анализа алгоритма

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

Очевидно, что рассматриваемый нами алгоритм простого выбора будет весьма эффективно сортировать массивы, состоящие из значений, типы которых позволяют выполнить ЭВМ наискорейший поиск минимума. Также стоит отметить, что данный алгоритм весьма рационален при использовании на ЭВМ, процессоры которых ориентированы на операции с массивами чисел и имеют встроенную операцию быстрого поиска минимума в массиве.

Отметим также, что использование такого способа реализации алгоритмов сортировки, как шаблоны функций С++ является очень выгодным. Данный способ позволяет быстро использовать созданную однажды и добавленную в библиотеку функцию, реализующую сортировку, в любой программе и для массивов любого размера и типа значений.

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

ЗАКЛЮЧЕНИЕ

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

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

Можно утверждать, что залогом успешности информационной системы, которая нуждалась бы в использовании методов, проанализированных нами, является способность этой системы производить полноценный анализ оперируемых данных. Безусловно, рациональность использования различных методов сортировки обусловлена имеющимися данными о сортируемых элементах. На основе анализа различных алгоритмов сортировки можно выделить несколько факторов, на которые стоит обращать внимание, прибегая к использованию того или иного алгоритма.

- Среднее время выполнения алгоритма

- Наибольшее значение времени выполнения алгоритма

- Объем занимаемой оперативной памяти

- Скорость оперирования сортируемыми данными

- Специфичность области и среды применения алгоритма

Сопоставляя алгоритмы быстрой и пирамидальной сортировок, что при небольшом количестве сортируемых элементов один алгоритм явно выигрывает у другого, но при значительном увеличении числа элементов первый алгоритм проигрывает второму. Также необходимо учитывать то, что некоторые алгоритмы, такие как выбор из дерева или пирамидальная сортировка ввиду того, что оперируют большим количеством информации, будут работать быстрее, но при этом занимать гораздо больше оперативной памяти ЭВМ, что в ряде случаев может быть нерационально. С другой стороны, стоит подстраивать используемый алгоритм под соответствующую архитектуру ЭВМ, специфичность ее процессора и т. п.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Ашарина, И.В. Основы программирования на языках C и C++ / И.В. Ашарина. - М.: ГЛТ, 2012. - 208 c.
2. Богачев, К.Ю. Основы параллельного программирования: Учебное пособие / К.Ю. Богачев. - М.: Бином, 2014. - 342 c.
3. Биллиг, В. Основы программирования на C# / В. Биллиг. - М.: Бином. Лаборатория знаний, 2006. - 483 c.
4. Гуриков, С.Р. Основы алгоритмизации и программирования на Python: Учебное пособие / С.Р. Гуриков. - М.: Форум, 2018. - 384 c.
5. Голицына, О.Л. Основы алгоритмизации и программирования: Учебное пособи / О.Л. Голицына, И.И. Попов. - М.: Форум, 2013. - 205 c.
6. Дорогов, В.Г. Основы программирования на языке С: Учебное пособие / В.Г. Дорогов, Е.Г. Дорогова. - М.: Форум, 2015. - 320 c.
7. Колдаев, В.Д. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагарина. - М.: ИД ФОРУМ, ИНФРА-М, 2012. - 416 c.
8. Колдаев, В.Д. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев. - М.: Форум, 2015. - 352 c.
9. Культин, Н.Б. Основы программирования в Turbo C++ / Н.Б. Культин. - СПб.: BHV, 2013. - 464 c.
10. Серкова, Е.Г. Основы алгоритмизации и программирования (ОП.04): практикум / Е.Г. Серкова. - Рн/Д: Феникс, 2017. - 159 c.
11. Семакин, И.Г. Основы алгоритмизации и программирования. Практикум: Учебное пос. для студ. учреждений сред. проф. образования / И.Г. Семакин, А.П. Шестаков. - М.: ИЦ Академия, 2013. - 144 c.
12. Черпаков, И.В. Основы программирования: Учебник и практикум для прикладного бакалавриата / И.В. Черпаков. - Люберцы: Юрайт, 2016. - 219 c.
13. Фридман, А.Л. Основы объектно-ориентированного программирования на языке Си++ / А.Л. Фридман. - М.: Гор. линия-Телеком, 2012. - 234 c.

ПРИЛОЖЕНИЕ

Разработанная программа