Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
ГЛАВА 2. Эффективность методов
|
|
2.1 Сравнение методов сортировки
Чтобы оценить время работы алгоритмов использовалась программа, которая формировала массив случайных целых чисел на отрезке [0, 50000] целых чисел, а затем сортировала этот массив каждым из алгоритмов сортировки. Были получены результаты для массивов с количеством элементов от 1000 до 20000 с интервалом 1000. В таблице 3 представлены усредненные результаты, полученные в ходе их проведения.
Таблица 3.
Время сортировки
| Количество элементов | Метод сортировки | |||||
| Обменами, мс | Вставками, мс | Пирамиды, мс | Быстрая, мс | |||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
| … | ||||||
Проанализировав полученные результаты, можно сделать несколько выводов. Несложно заметить, что наилучшую скорость работы показал алгоритм сортировки Хоара. Так же хорошую скорость показал метод сортировки Уильямса-Флойда. Когда количество элементов массива не превышало 50 000, упорядочивание происходило практически мгновенно, остальные алгоритмы показали не высокую скорость работы и применение их при разработке серьезных программ не допустимо.
Методы сортировки Уильямса-Флойда и Хоара это в своём роде улучшение алгоритмов выбора и обмена. Поэтому сравним их попарно.
На рисунке 1 представлен график зависимости времени работы от количества элементов методов обмена и выбора.
|
Рисунок 1. График зависимости времени работы от количества элементов методов обмена и выбора(синяя- метод обмена, красная - метод выбора).
Из рисунка 1 видно, что метод сортировки выбором работает быстрее для большого количества элементов.
На рисунке 2 представлен график зависимости времени работы от количества элементов методов Хоара и Уильямса-Флойда. Алгоритм Хоара или как его ещё называют алгоритм быстрой сортировки показал более высокую скорость и признан лучшим алгоритмов сортировки массивов из представленых.
|
Рисунок 2. График зависимости времени работы от количества элементов методов Хоара и Уильямса-Флойда(синий-Уильямса-Флойда, красный- Хоара).
2.2 Применение методов
Трудно назвать какой-то метод лучшим какой-то худшим. Для каждой ситуации нужно подобрать более удобный метод. Например метод сортировки обменами легко реализовать. И если нужно упорядочить небольшое количество элементов, то он более предпочтителен.
Метод сортировки Хоара достаточно трудно реализовать. Он работает по принципу рулетки и зависит от выбора граничного элемента. При неудачном выборе граничного числа он работает медленно.
|
|