ВУЗ:
Составители:
113
проходе. Отсутствие перестановок говорит о том, что последовательность уже
упорядочена, и процесс можно прекратить.
i A(i) Пр.1 Пр.2 Пр.3 Пр.4 Пр.5 Пр.6 Пр.7 Пр.8 Пр.9
1 15 11 11 9 7 2 2 2 2 1
2 11 12 9 7 2 5 3 3 1 2
3 12 9 7 2 5 3 5 1 3 3
4 9 7 2 5 3 7 1 5 5 5
5 7 2 5 3 8 1 7 7 7 7
6 2 5 3 8 1 8 8 8 8 8
7 5 3 8 1 9 9 9 9 9 9
8 3 8 1 11 11 11 11 11 11 11
9 8 1 12 12 12 12 12 12 12 12
10 1 15 15 15 15 15 15 15 15 15
Рис. 8.2. Пример сортировки методом обмена
Число сравнений метода обмена зависит от числа проходов для сорти-
ровки. В худшем случае, если исходная последовательность имеет обратную
упорядоченность, за каждый i-й проход выполняются перестановки, а число
проходов равно N–1. Тогда для сортировки потребуется максимальное число
сравнений, равное сумме членов арифметической прогрессии:
С
max
= (N–1) + (N–2) + (N–3) + . . . + 1
или
N-1
C
max
= Σ (N–i) = 0,5N(N–1).
i=1
В лучшем случае, когда исходная последовательность уже упорядочена,
потребуется один проход и N–1 сравнение. Минимальное число сравнений C
min
= N–1. Среднее число сравнений пропорционально 0,25N
2
.
Число обменов при этом способе зависит от степени упорядоченности
исходной последовательности. Если она полностью упорядочена, то обменов
нет. Максимальное число обменов будет при обратном порядке элементов в
исходной последовательности. В этом случае обмен происходит при каждом
сравнении и общее их число П
max
= 0,5N(N–1). Среднее число обменов пропор-
ционально 0,25N
2
.
Для примера, показанного на рис. 8.2, число сравнений соответствует
худшему случаю C = С
max
= 0,5·10(10–1)=45. Среднее число обменов, вычислен-
ное по аппроксимированной формуле П
ср
= 0,25·10
2
=25. Фактическое число об-
менов равно 38.
Страницы
- « первая
- ‹ предыдущая
- …
- 111
- 112
- 113
- 114
- 115
- …
- следующая ›
- последняя »