76
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
=
=
+−= +
=
n
j
j
n
j
j
d
n
d
2
2
) (
1 )1 (
C
,
число перестановок:
=
=
+− = +
=
n
j
j
n
j
j
d
n
d
2
2
) (
2 2 )2 (
П
.
Заметим, что для любого
j
1
0
−≤ ≤
j
d
j
и
d
j
независимы.
Для лучшего случая, когда таблица изначально упорядочена:
1
C
min
−=
n
;
2 2 П
min
− =
n
.
Для среднего случая:
)1 (
4
1 C
ср
− =
nn
;
)8 )(1 (
4
1 П
ср
+ − =
n n
.
Для худшего случая, когда таблица изначально упорядочена в обратном
порядке:
)2 )(1 (
2
1 C
max
+ − =
n n
;
)4 )(1 (
2
1 П
max
+ − =
n n
.
5.2. Сортировка перестановками (обмен)
Обменная сортировка некоторым систематическим образом меняет
местами пары имен, не отвечающие порядку до тех пор, пока такие пары
существуют. Фактически алгоритм можно рассматривать как обменную
сортировку, в которой имя
x
j
меняется местами со своим соседом слева до тех
пор, пока не оказывается на правильном месте. В этом разделе мы обсуждаем
два типа обменных сортировок: хорошо известную, но относительно
неэффективную пузырьковую сортировку и быструю сортировку — один из
лучших со всех точек зрения алгоритмов внутренней сортировки.
5.2.1. Метод пузырька (пузырьковая сортировка)
Второй ключ сравниваем с первым; если их положение не соответствует
заданному порядку, то меняем их местами. Третий ключ сравниваем со вторым:
если они меняются местами, то сравниваем с первым и т.д.
1...,68,69,70,71,72,73,74,75,76,77 79,80,81,82,83,84,85,86,87,88,...106