АЛГОРИТМЫ

Новости

Рассылка новостей

Форум

AlgoPascal

Редактор блок-схем

Статьи

О сайте

Контакты

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

Автор:Быстрицкий В.Д.

На странице сортировки массивов представлены 5 алгоритмов:

в данной статье я постараюсь проанализировать скорость их работы. Начнем со статистики скорости работы алгоритмов на массивах различной длины.

Чтобы оценить время работы алгоритмов использовалась программа, которая формировала массив псевдослучайных равномерно распределенных на отрезке [0,100000] целых чисел, а затем сортировала этот массив каждым из алгоритмов сортировки. Были получены результаты для массивов с колличеством элементов: 5000, 10000, 25000, 50000, 100000. Для каждой размерности были проведены по 5 экспериментов, в таблице представлены усредненные результаты полученные в ходе их проведения:

Количество элементов Метод сортировки

Пузырька Простых вставок Бинарных вставок Шелла Бинарных деревьев

5000 570 242 154 54 1

10 000 2 352 990 570 208 1

25 000 17 160 9 062 4 710 1 194 1

50 000 77 234 44 940 22 322 5 978 98

100 000 321 169 190 062 102 228 24 648 208

Проанализировав полученные результаты, можно сделать несколько выводов. Во-первых несложно заметить, что наилучшую скорость работы показал алгоритм сортировки бинарными деревьями при этом в случае когда количество элементов массива не превышала 50 000 упорядочивание происходило практически мгновенно, остальные алгоритмы показали не высокую скорость работы и применение их при разработке серьезных программ не допустимо. Во-вторых время работы первых четырех алгоритмов ("пузырька", Шелла,простых и бинарных вставок) растет квадратично относительно роста размера упорядочиваемого массива, что подтверждается и теоретическими соображениями, известно, что скорость работы данных алгоритмов оценивается как O(n²). Сортировка методом Шелла показала вполне сносные результаты, но при этом все таки худшие нежели сортировка методом бинарных деревьев.

Таким образом можно сделать вывод, что при разработке программ требующих упорядочивания массивов большого объема следует применять сортировку методом бинарных деревьев, как имеющую существенно лучшие показатели по скорости работы.