Сортировка слиянием

Ожидаемая трудоемкость: 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/]