Маргинальные свойства сортировки массивов методом дихотомической вставки
7
было бы использовать деление на два, но оно медленное. Поэтому
его часто заменяют сдвигом
>>1
на один бит вправо:
2,2min
2,2max
2
2
3 1 3;
3 ]log [ 3]log [
W
W
n
n
= ⋅ =
= ⋅
=
.
Следующая инструкция условия
if
(
m == a
[
z
])
{
n
1
= z; break;
}
проверяет окончание поиска. На выполнение условия
m == a
[
z
]
затрачиваются две операции. Если условие истинно, то поиск
завершен и следует выполнить составную инструкцию {
n
1
= z;
break;
} с одной операцией присваивания. Если условие ложно, то
никаких дополнительных действий в инструкции не производится. В
маргинальных ситуациях эта инструкция условия проявляет себя
следующим образом. Минимальный поиск происходит, когда на
первой итерации обнаруживается поисковый элемент:
(
)
2,3min
1 1 1 2
W
= ⋅ + =
.
Максимальный поиск — когда произойдут все дихотомические
действия, но результата сравнения нет:
2,3max
2
2
]log [ 1 ]log [
W
n
n
=
⋅ =
.
Следующая инструкция альтернативного условия
if
(
m < a
[
z
])
n
2
= z –
1
; else n
1
= z +
1 проясняет, в какой части массива следует
продолжать поиск. В любом случае будут выполняться две операции
в условии
m < a
[
z
] и две альтернативные операции
n
2
= z –
1 или
n
1
= z +
1:
(
)
2,4
2
2
2 2 ]log [ 4]log [
W
n
n
= + ⋅
=
.
После рассмотрения всех инструкций подведем итог. Минималь-
ный поиск осуществляется, когда сразу происходит совпадение цен-
трального элемента с поисковым элементом. Реально такая ситуация
возникает тогда, когда массив содержит одинаковые элементы.
min
1
2,1min
2,2min
2,3min
3 1 3 2 9
DichPos
W W W W W
= +
+
+
= + + + =
.
Максимальное количество операций затрачивается при выполне-
нии всех итераций дихотомии:
max
1
2,1max
2,2max
2,3max
2,4
2
2
2
2
2
3 ]log [ 3]log [ ]log [ 4]log [ 3 9]log [.
DichPos
W W W W W W
n
n
n
n
n
= +
+
+
+ =
= +
+
+
+
= +
.
Теперь можно определить количество операций, выполняемых в
сортировке с дихотомическим поиском
SortInsertDich().
На первом
