А.Ф. Деон, Ю.И. Терентьев
10
Это ситуации, когда исходный массив уже был упорядоченным, а
также, когда массив редко частично обновляется. По максимальному
количеству операций метод дихотомической вставки работает быст-
рее, чем последовательная вставка:
(
)
2
max
2
max
2
13 23 16;
2
2
7
17
9 1 ]log [
15.
2
2
SortInsertSeq
SortInsertDich
W
n
n
W
n n
n n
= + −
= + −
+ −
Непосредственный расчет этих оценок представлен в следующей
таблице.
Число
элементов
n
max
SortInsertSeq
W
max
SortInsertDich
W
max
max
SortInsertSeq
SortInsertDich
S
S
4
135
129
1,047
8
493
466
1,058
16
1833
1557
1,177
32
7009
5236
1,339
64
27345
18267
1,497
128
109953
66418
1,655
256
428913
249897
1,716
512
1709809
963232
1,775
1024
6827505
3770775
1,811
Главными коэффициентами в этом сравнении являются коэффи-
циенты при
n
2
. Быстродействие метода дихотомической сортировки
выглядит предпочтительнее. Но эти оценки — для наихудших случаев
расположения информации в массиве. Для обеих технологий это мас-
сив с обратно упорядоченным расположением значений элементов.
ЛИТЕРАТУРА
[1] Кнут Д.Э.
Искусство программирования. Т. 3. Сортировка и поиск
.
Москва, изд-во Вильямс, 2009, 824 с.
[2] Седжвик Р.
Фундаментальные алгоритмы на С++. Анализ, структуры
данных, сортировка, поиск
. Санкт-Петербург, ООО «ДиаСофтЮП», 2002,
688 с.
Статья поступила в редакцию 10.06.2013
Ссылку на эту статью просим оформлять следующим образом:
Деон А.Ф., Терентьев Ю.И. Маргинальные свойства сортировки масси-
вов методом дихотомической вставки.
Инженерный журнал: наука и инно-
вации
, 2013, вып. 6. URL:
