ё ft

Рис. 14. Процесс сортировки методом пузырька.

позицию; таким образом, можно отметить, что в начале сортировки еще ничего не известно о порядке размещения записей.)

82. [Цикл по j.] Присвоить t 0. Выполнить шаг ВЗ при j = 1, 2, ..., BOUND - 1. Затем перейти к шагу В4. (Если BOUND = 1, то сразу перейти к В4.)

83. [Сравнение/обмен Rj -.Rj+i.] Если Kj > Kj+i, то поменять местами Rj О Rj+i и установить t <- j.

84. [Были ли обмены?] Если t = 0, завершить выполнение процедуры. В противном случае присвоить BOUND <- t и возвратиться к шагу В2.

В1. Начальная установка BOUND

В2. Цикл по j

j = BOUND

(ВА.

l<j<BOUND

ВЗ. Сравнение/обмен Rj-.Rji

Были ли обмены?

Рис. 15. Блок-схема сортировки методом пузырька.

Программа В (Метод пузырька). Как и в предыдущих MIX-программах этой главы, полагаем, что сортируемые записи находятся в ячейках от INPUT+1 до INPUT+N.

если t > 0. I

Анализ метода пузырька. Очень полезно исследовать время работы алгоритма В. Оно определяется тремя параметрами: числом проходов А, числом обменов В и числом сравнений С. Если исходные ключи различны и расположены в случайном порядке, можно предположить, что они образуют случайную перестановку множества {1,2, Понятие таблица инверсий (раздел 5.1.1) приводит к простому способу описания эффекта, достигаемого на каждом проходе при сортировке методом пузырька.

Теорема I. Пусть ai аг ... а„ -перестановка множества {1,2,..., п}, а bi • • • Ь„ - соответствующая таблица инверсий. Если в результате очередного прохода при сортировке методом пузырька, (алгоритм В) перестановка ai аг ... а„ преобразуется в а[ «2 ... ajj, то соответствующая таблица инверсий Ь[ • • К получается из bi • • • Ь„ в результате уменьшения на единицу каждого ненулевого элемента.

Доказательство. Если перед ai имеется больший элемент, то щ поменяется местами с наибольшим из предшествующих элементов, так что Ьа, уменьшится на единицу. С другой стороны, если перед aj нет элемента, большего ai, то ai никогда не поменяется местами с большим элементом, так что 6а; останется равным нулю.

Итак, можно разобраться в том, что происходит в процессе сортировки методом пузырька, изучая последовательность таблиц инверсий между проходами. Вот как выглядят, например, таблицы инверсий для рис. 14.

3183450403223210

2072340302112100 Проход 2 (1)

1061230201001000

0050120100000000

Проход 1 Проход 2 Проход 3

Поэтому, если Oi 02 • • • Oji - таблица инверсий исходной перестановки, то должны выполняться равенства

A = l + max{bi,b2,...,bn), (2)

В = bi+b2 + --- + bn, (3)

C = Ci +С2 + --- + СЛ, (4)

где Cj - значение BOUND - 1 перед началом j-ro прохода. Используя таблицы инверсий, запишем

Cj - шах {bi + i\ bi> j -1} - j (5)

(см. упр. 5). Следовательно, в примере (1) Л = 9, В = 41, С = 15 + 14 + 13 + 12 + 7 + 5 + 44-3 + 2 = 75. Общее время сортировки на машине MIX для случая, показанного на рис. 14, равно 960и.

Распределение величины В (суммарного числа инверсий в случайной перестановке) нам уже хорошо известно; значит, остается проанализировать величины А и С.

Вероятность того, что А < к, равна произведению 1/п! и числа таблиц инверсий, не содержащих компонент > А;, а именно - к"~к\ при 1 < А; < п. Следовательно, вероятность того, что потребуется ровно к проходов, равна

Ak {к-к] -{к- 1)"-=+! (А; - 1)!). (6)

Теперь можно вычислить среднее значение А;Л. Выполнив суммирование по частям, получаем

Aave = n+1-X, -j- =n+l-P(n), (7)

где P{n) - функция, асимптотическое поведение которой, как следует из соотношения 1.2.11.3-(24), описывается формулой у/тгп/2 - + 0{1/л/п). Формула (7) была представлена без доказательства в работе Е. Н. Friend, J.4CM 3 (1956), 150; доказательство в своей докторской диссертации привел Говард Б. Демут (Howard В. Demuth) [Ph. D. Thesis (Stanford University, October, 1956), 64-68]. Стандартное отклонение величины A представлено в упр. 7.

Проанализировать суммарное число сравнений С несколько сложнее, поэтому рассмотрим только среднее значение Cave- Пусть fj{k) - число таких таблиц инверсий bi .. .Ьп {п фиксировано), что при 1 < г < п либо bi < j - либо bi+i-j < к; тогда

/,(fc) = (j+A;)!(i-l)"->-= для0<А;<гг- (8)

(см. упр. 8). Среднее значение Cj в (5) равно {Ylk[fj{k) - fj{k- l)))/n\. Суммируя по частям, а затем по j, получаем формулу

l<J<n 0<r<s<n

0<k<n-j

Определить асимптотическое значение здесь не так просто, и мы вернемся к нему в конце этого раздела. Подводя итог анализу метода пузырька, запишем формулы, вьшеденные выше (а также ниже), следующим образом: