Сортировка слиянием
Ожидаемая трудоемкость: O(n log n)
Рис 7. График зависимости времени сортировки от количества сортируемых элементов для сортировки слиянием
Рис 8. График отношения времени сортировки к функции n log n в зависимости от количества сортируемых элементов Сравнение сортировок
Рис 9. Сравнение времени сортировок на одном массиве Заключение В ходе выполнения лабораторной работы были реализованы две программы: Exp.exe, осуществляющая сортировку массива, и Tests.exe, проводящая серийный запуск Exp.exe. Обе программы удовлетворяют всем требованиям, представленным в разделе «Постановка задачи». По результатам экспериментов было построено 7 графиков. Рисунки 3, 5, 7 демонстрируют зависимость времени сортировки от числа элементов в сортируемом массиве для соответствующих методов. Рисунки 4, 6, 8 показывают, что ожидаемая трудоемкость для каждой из сортировок совпадает с реальной, так как функция отношения времени сортировки к ее ожидаемой трудоемкости ведет себя аналогично константе. Рисунок 9 позволяет сравнить скорость сортировки разными алгоритмами на одном массиве данных. По результатам этого сравнения наиболее быстрым алгоритмом стала сортировка слиянием.
Литература 1. Сортировка слиянием — Википедия. — [http://ru.wikipedia.org/wiki/Сортировка_слиянием] 2. Microsoft Developer Network. — [http://msdn.microsoft.com/]
|
