Экспериментальный анализ различных методов сортировки

Министерство науки и высшего образования Российской Федерации 

Федеральное государственное автономное образовательное учреждение высшего образования 

КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ 

Институт Вычислительной математики и информационных технологий 

Практическая работа по дисциплине

«Алгоритмы и анализ сложности»

 на тему: «Экспериментальный анализ различных методов сортировки»

Обучающийся :

гр. 09-931 Рахматуллина Эльвина

Преподаватель:

Васильев Александр Валерьевич

2021 г.

Введение

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

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

Методика сравнения

        Мы будем рассматривать следующие сортировки:

• Пузырьковая сортировка. Сложность в худшем и среднем случае .[pic 1]
• Сортировка вставками. Сложность в худшем и среднем случае .[pic 2]
• Сортировка выбором. Сложность в худшем и среднем случае .[pic 3]
• Сортировка Шелла. Сложность в худшем случае , в лучшем – .[pic 4][pic 5]
• Быстрая сортировка. Сложность в среднем случае .[pic 6]
• Сортировка слиянием. Сложность – .[pic 7]
• Сортировка кучей. Сложность – .[pic 8]
• Поразрядная сортировка. Сложность – .[pic 9]
• Встроенная сортировка. Функция sort из библиотеки algorithm, построенная на основе быстрой сортировки.

Сравнение алгоритмов происходило следующим образом: на языке C++ были реализованы выше упомянутые алгоритмы и были протестированы на разных типах данных и массивах различной длины (от 50 до 500 000). Каждый тест «прогонялся» 10 раз, для построения графиков были использованы средние значения. Сравнивать сортировки будем по скорости выполнения теста. Для оценки будет использована величина , где  - время выполнения программы в мс.[pic 10][pic 11]

В приложении 1 предоставлен код функций сортировок. В приложении 2 приведена таблица с результатами тестирования.

Массив целых случайных чисел

        Результат тестирования для массивов длин от 50 до 500000, наполненный случайными величинами:

[pic 12]        

[pic 13]

[pic 14]

[pic 15]

[pic 16]

На массивах с большим количеством элементов (5000-500000) лучше всего себя показывает поразрядная сортировка. Это можно объяснить тем, что в такой сортировке  практически отсутствуют вложенные циклы.  Также выделяется быстрая сортировка. При меньшем количестве элементов первые места занимает сортировка Шелла и сортировка вставками. Сортировка вставками показывает наилучший результат среди  простых схем, потому что ей не обязательно проходится по всех элементам массива во вложенном цикле. Сортировка Шелла быстрее сортировки вставками, что особенно видно на массиве с 500 элементами, потому что, грубо говоря, в сортировке Шелла элементы быстрее встают на свои места.

Массив целых чисел в диапазоне от 0 до 9

        В этот раз используются только числа со значениями в интервале [0;9].

[pic 17]

[pic 18]

[pic 19]

[pic 20]

[pic 21]

        Как и в прошлом тесте, на массиве с малым количеством элементов сортировка вставками показывает хорошие результаты. Возможно, это связано с тем, что в этом массиве хранится большое количество одинаковых элементов, и поэтому не так часто появлялась необходимость переставлять элементы. По степени увеличения числа элементов в массиве сортировка Шелла (на 500 элементов) и быстрая сортировка (на 5000 элементов и больше) вырываются вперед. Но лидером среди всех сортировок оказалась поразрядная сортировка. Это связано с тем, что числа в массиве имели всего один разряд, и хватило всего одного прохода по массиву, чтобы отсортировать элементы.