Стр. 78 - Основы алгоритмов и структур данных

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 и dj независимы.
Для лучшего случая, когда таблица изначально упорядочена:
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. Сортировка перестановками (обмен)
Обменная сортировка некоторым систематическим образом меняет
местами пары имен, не отвечающие порядку до тех пор, пока такие пары
существуют. Фактически алгоритм можно рассматривать как обменную
сортировку, в которой имя xj меняется местами со своим соседом слева до тех
пор, пока не оказывается на правильном месте. В этом разделе мы обсуждаем
два типа обменных сортировок: хорошо известную, но относительно
неэффективную пузырьковую сортировку и быструю сортировку — один из
лучших со всех точек зрения алгоритмов внутренней сортировки.
5.2.1. Метод пузырька (пузырьковая сортировка)
Второй ключ сравниваем с первым; если их положение не соответствует
заданному порядку, то меняем их местами. Третий ключ сравниваем со вторым:
если они меняются местами, то сравниваем с первым и т.д.