А.Ф. Деон, Ю.И. Терентьев
14
Сравнивая минимальные результаты сортировки методом после-
довательной вставки и модифицированным методом парных сравне-
ний для уже упорядоченного исходного массива, получаем, что быст-
родействие сортировки модифицированным методом парных
сравнений превосходит быстродействие сортировки методом последо-
вательной вставки (
n
> 7):
min
min
5 7
2 6 .
SortInsertSeq
SortPairMod
W
n W
n
Если исходный массив упорядочен в обратном направлении,
быстродействие сортировки методом выбора выше, чем быстродей-
ствие сортировки методом последовательной вставки:
2
2
max
max
21 7
23 13
10
16
.
2 2
2 2
SortChoice
SortInsertSeq
W
n n W
n n
Сортировка методом дихотомической вставки.
В предыдущем
алгоритме метода последовательной вставки предусмотрено посте-
пенное увеличение размера левой упорядоченной части. На каждой
итерации в этой части происходит поиск места вставки очередного
сортируемого элемента из правой части. Поскольку левая часть явно
упорядочена, то процесс поиска места вставки можно ускорить, если
воспользоваться максимальным по быстродействию методом дихо-
томии [3].
Минимальная оценка этого метода сортировки [3]
min
5 7 ,
SortInsertDich
W
n
а максимальная оценка определяется выражением [3]
2
max
2
17 7
15 9 1 log
.
2 2
SortInsertDich
W
n
n n n
Открытые квадратные скобки обозначают округление до ближайшего
большего целого числа.
Сравнивая результаты сортировки, получаем
min
min
2 6
5 7 ;
SortPairMod
SortInsertDich
W
n W
n
2
max
max
21 7
10
2 2
SortChoice
SortInsertDich
W
n n W
2
2
17 7
15 9 1 log
.
2 2
n
n n n
Выводы.
Формулы для оценки количества операций всех рас-
смотренных сортировок в предельных условиях сведены в таблицу.
Главными коэффициентами в сравнениях по быстродействию явля-
ются коэффициенты при
2
n
.
