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

Сравним эффективность методов сортировки массивов. Для всех прямых методов сортировки можно дать точные аналитические формулы [3]. Они представлены в табл. 3.5.

Для усовершенствованных методов сортировки нет простых и точных формул. Существенно, однако, что в случае сортировки Шелла вычислительные затраты составляют с-п ' , а для пирамидальной и быстрой сортировок — с и log п, где с — соответствующий коэффициент.

Опытным путем были получены следующие результаты [3]:

1. Пузырьковая сортировка наихудший метод из всех сравниваемых.

2. Быстрая сортировка лучше в 2—3 раза, чем пирамидальная. Она сортирует массив, расположенный в обратном порядке, практически с той же скоростью, что и уже упорядоченный.

Таблица 3.5 Сравнение прямых методов сортировки

 

Вид сортировки	Показатели	Min	Среднее	Мах
Прямое включение	С = М =	п- 2(и - 1)	(п2 - п -2)1 А (п2-9п-Щ1А	(п2 - п)12 - 1 (п2 -Ъп- 4)/2
Прямой выбор	с = м=	(п2 - п)12 3(и - 1)	(п2 - п)12 «■(In n + 0,57)	(п2 - п)12 п2 /4+ 3(«-1)
Прямой обмен	с = м=	(п2 - п)12 0	(п2 - п)12 0,75-(п2-п)	(п2 - п)12 (п2-п),5