Результат определения эффективности алгоритмов

Ниже представлены графики зависимсоти времени выполнения различных алгоритмов сортировки от размерностей исходных массивов. Указанное время соответствует повторениям алгоритмов сортировки 1000000 раз. На рис. 5.1. представлен график для способа заполнения исходных массивов в обратном порядке (худший случай). На рис. 5.2. представлен график для способа заполнения в случайном порядке.

На рисунках изображены фрагменты Формы GrafForm при работе курсовой программы.

Рис. 4.1. График зависимости времени от размерности массива для убывающего порядка заполнения

Рис. 4.2. График зависимости времени от размерности массива для случайного порядка заполнения

Из графиков видно, что лидирующую позицию при любых изначальных данных занимает Быстрая сортировка. Сортировка методом Пузырька – самая неэффективная. Хорошую эффективность показывает метод сортировки Вставками, причем при случайном заполнении исходного массива, метод сортировки Вставками практически не уступает по скорости Быстрому методу. Наиболее эффективные методы сортировки Вставками и Быстрая, при этом метод Вставками не использует дополнительной памяти, в отличие от Быстрого метода, алгоритм которого при каждом проходе рекурсивно вызывается и заполняет стек, к тому же Быстрый метод неустойчив.

При случайном заполнении эффективность сортировки двух методов (Быстрая и Вставками) практически одинаковая, однако, метод Вставок здесь имеет ряд приемуществ – не используется доп.память и он устойчив, т.е. не меняет расположение одинаковых элементов.

При заполнении в обратном порядке (худший случай) – бесспорный лидер – метод быстрой сортировки.

Из всего этого можно сделать вывод, что из методов сортировки Вставками и Быстрая сложно определить как лучшая или худшая, т.к. при известном способе заполнения исходных данных можно применять тот или иной метод сортировки.

Ниже представлена таблица результатов поиска в массиве. В качестве искомого элемента выбран приблизительно центральный элемент массива. Кол-во элементов массива - 20:

Таблица 1

Ниже представлена таблица результатов поиска последнего элемента массива. (Всего 20 эл.):

Таблица 2

Согласно данным таблиц, можно сделать следующее заключение. Способ прямого перебора самый неэффективный, однако очень простой в реализации. Его целесообразно использовать для очень маленьких массивов. А вот Бинарный и Интерполяционный способы показывают различные непредстказуемые результаты, в зависимости от положения искомого элемента. Так, как Интерполяционный способ наиболее эффективен при значениях массива, возрастающими приблизительно в арифметической прогрессии, то от содержания и равномерности распределения данных в массиве зависит его эффективность, а значит, Интерполяционный метод лучше всего использовать для больших массивов, делая несколько итераций, а дальше использовать бинарный или прямой методы.