Недавно был разработан алгоритм быстрой сортировки, сложность которого определяется как 2*N (2 умножить на N).
В данной статье не будем разбирать сам алгоритм сортировки, а, только проведя серию тестов, сравним его с сортировкой, используемой в Visual Studio (функция std::sort). Как говорится: только факты и минимум эмоций.
Сортировать будем текстовую информацию, в качестве которой будем рассматривать массив слов. Данный массив будем формировать на основе литературных произведений. Для этого все слова данных произведений по порядку заведем в данный массив. Разбиение на слова происходит без модернизации, признаком начала нового слова является пробел. Слова в массиве полностью соответствуют словам в тексте. Так как знаки препинания (точка, запятая и так далее) и управляющие символы пишутся за словами без пробелов, то, как следствие, они являются частью слов. Отдельно стоящие знаки препинания и управляющие символы рассматриваются как самостоятельные слова. В файлах присутствуют адреса сайтов, где эти файлы находятся. Данные адреса являются одним словом. Самое длинное слово состоит из 95 символов. В рассматриваемых произведениях присутствуют буквы латинского алфавита, кириллицы, знаки препинания и управляющие символы.
Сортируемая информация является произвольной, никаким образом не упорядоченной, и, как следствие, специальные сортировки не применяются.
Сравниваются два метода сортировки: вновь разработанный алгоритм сортировки со сложностью 2*N и алгоритм, используемый в Visual Studio 2017 (функция std::sort). Интересуют время сортировки и количество используемой для этого памяти каждого из методов на каждом тесте.
Программы написаны в среде — Visual Studio 2017, на платформе — Windows x64. Тестирование проводилось в 2-х конфигурациях. Результаты тестирования в конфигурации Debug и конфигурации Release представлены в таблицах 1 и 2 соответственно. В таблицах представлены результаты тестирования двух методов сортировки.
Так как результаты по времени вычисления — плавающие (значения меняются в пределах 10%), то по каждому тесту проводилась серия вычислений, из которых выбирались наименьшие значения и эти значения ставились в таблицы. Время, указанное в 4 и 6 колонках, является только временем сортировки. Дополнительные процессы (такие как считывание и запись в файл, формирование массива) в указанное время не входят.
Эффективность по времени
и по памяти 
рассчитывается по следующим формулам соответственно:
где
— количество временных тактов, за которые выполняется функция std::sort, используемой в Visual Studio, и новый алгоритм сортировки соответственно; 
— количество используемой памяти, необходимой для выполнения функции std::sort, используемой в Visual Studio, и нового алгоритма сортировки соответственно.
Таблица 1.
Таблица 2.
Насколько вновь разработанный алгоритм сортировки со сложностью 2*N является более эффективным (как по времени, так и использованию памяти) алгоритма, используемого в Visual Studio 2017 (функция std::sort) судите сами.
В данной статье не будем разбирать сам алгоритм сортировки, а, только проведя серию тестов, сравним его с сортировкой, используемой в Visual Studio (функция std::sort). Как говорится: только факты и минимум эмоций.
Сортировать будем текстовую информацию, в качестве которой будем рассматривать массив слов. Данный массив будем формировать на основе литературных произведений. Для этого все слова данных произведений по порядку заведем в данный массив. Разбиение на слова происходит без модернизации, признаком начала нового слова является пробел. Слова в массиве полностью соответствуют словам в тексте. Так как знаки препинания (точка, запятая и так далее) и управляющие символы пишутся за словами без пробелов, то, как следствие, они являются частью слов. Отдельно стоящие знаки препинания и управляющие символы рассматриваются как самостоятельные слова. В файлах присутствуют адреса сайтов, где эти файлы находятся. Данные адреса являются одним словом. Самое длинное слово состоит из 95 символов. В рассматриваемых произведениях присутствуют буквы латинского алфавита, кириллицы, знаки препинания и управляющие символы.
Сортируемая информация является произвольной, никаким образом не упорядоченной, и, как следствие, специальные сортировки не применяются.
Сравниваются два метода сортировки: вновь разработанный алгоритм сортировки со сложностью 2*N и алгоритм, используемый в Visual Studio 2017 (функция std::sort). Интересуют время сортировки и количество используемой для этого памяти каждого из методов на каждом тесте.
Программы написаны в среде — Visual Studio 2017, на платформе — Windows x64. Тестирование проводилось в 2-х конфигурациях. Результаты тестирования в конфигурации Debug и конфигурации Release представлены в таблицах 1 и 2 соответственно. В таблицах представлены результаты тестирования двух методов сортировки.
Так как результаты по времени вычисления — плавающие (значения меняются в пределах 10%), то по каждому тесту проводилась серия вычислений, из которых выбирались наименьшие значения и эти значения ставились в таблицы. Время, указанное в 4 и 6 колонках, является только временем сортировки. Дополнительные процессы (такие как считывание и запись в файл, формирование массива) в указанное время не входят.
Эффективность по времени
и по памяти рассчитывается по следующим формулам соответственно:
где
— количество временных тактов, за которые выполняется функция std::sort, используемой в Visual Studio, и новый алгоритм сортировки соответственно; — количество используемой памяти, необходимой для выполнения функции std::sort, используемой в Visual Studio, и нового алгоритма сортировки соответственно.Таблица 1.
Таблица 2.
Насколько вновь разработанный алгоритм сортировки со сложностью 2*N является более эффективным (как по времени, так и использованию памяти) алгоритма, используемого в Visual Studio 2017 (функция std::sort) судите сами.