Маргинальные свойства сортировки массивов методом дихотомической вставки
5
Складывая оценки составных частей пятого этапа, получаем
(
)
(
)
(
)
(
)
5
5,1
5,2
5,3
5,4
2
7
7 5
2 1 2 1
1 2 1
6.
2
2 2
W W W W W
n
n
n n
n
n n
= + + + =
= − + − + − + − = + −
Таким образом, рассчитаны составные оценки для всех частей ал-
горитма. Минимальное количество затрачиваемых операций получа-
ется, когда предоставлен уже упорядоченный массив. Обозначим ми-
нимальную оценку сортировки методом последовательной вставки в
функции
SortInsertSeq()
как
(
)
min
1
2
3 1 4 1 7 5
SortInsertSeq
W
W W n
n
n
= + = − + − = −
.
Максимальную оценку дает следующее выражение:
(
)
(
)
max
1
2
3
4
5
2
2
2
7 5
13 23
3 1 4 1 3 3 2 1
6
16.
2 2
2
2
SortInsertSeq
W
W W W W W
n
n
n
n
n n
n
n
= + + + + =
= − + − + − + − + + − = + −
Общим итогом для сортировки методом последовательной встав-
ки является то, что его применение целесообразно для частично упо-
рядоченных массивов. Такая ситуация наблюдается, когда информа-
ционная система поддерживает постоянно упорядоченный массив, в
котором редко изменяются значения.
Сортировка методом дихотомической вставки.
Алгоритм ме-
тода последовательной вставки постепенно увеличивает размер левой
упорядоченной части. На каждой итерации в ней происходит поиск
места вставки очередного сортируемого элемента из правой части.
Поскольку левая часть явно упорядочена, то процесс поиска места
вставки можно ускорить, если воспользоваться максимальным по
быстродействию методом дихотомии. Ниже представлена функция
SortInsertDich()
, которая повторяет функцию последовательной
вставки с заменой внутреннего цикла поиска места вставки на дихо-
томическую функцию поиска. Для удобства программирования и по-
нимания алгоритма дихотомический поиск вынесен в отдельную
функцию
DichPos()
. Для того чтобы в результирующей скомпилиро-
ванной программе исключить явную операцию вызова функции
DichPos()
, она снабжена модификатором
inline
, который предписыва-
ет компилятору вместо вызова функции поставить ее тело.
inline int DichPos( const int a[], const int j )
{
int n1 = 0, n2 = j — 1; // начало и конец массива
while( n1 <= n2 ) // цикл поиска
{
