Стр. 77 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
75
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Начальные ключи 44 55 12 42 94 18 06 67
i
= 2 44 55 12 42 94 18 06 67
i
= 3 12 44 55 42 94 18 06 67
i
= 4 12 42 44 55 94 18 06 67
i
= 5 12 42 44 55 94 18 06 67
i
= 6 12 18 42 44 55 94 06 67
i
= 7 06 12 18 42 44 55 94 67
i
= 8 06 12 18 42 44 55 67 94
for (j=
2
; j<=n; j++)
{
xx = x
j
;
for (i=j-
1
; i>=
1
; i --)
{
if (xx<x
i
) break;
x
i+
1
= x
i
;
}
x
i+
1
= xx;
}
Эффективность данного алгоритма, как и большинства алгоритмов
сортировки, зависит от числа сравнений имен и числа пересылок данных,
осуществляемых в трех случаях: худшем, среднем (в предположении, что все
n
!
перестановок равновероятны) и лучшем. Для анализа данного алгоритма
введём обозначения :
Пусть
d
j
– число ключей, больших, чем
x
j
,
и стоящих слева от него (число
инверсий).
Пример:
44 55 12 42 94 18 06 67
d
1
=0;
d
2
=0;
d
3
=2;
d
4
=1;
d
5
=0;
d
6
=4
d
7
=6;
d
8
=1.
На каждой итерации
j
внешнего цикла будет
d
j
+2
перестановки и
d
j
+1
сравнений. Тогда на всех (
n
-1) итерациях число сравнений будет:
