Таблица 1

ЗНАЧЕНИЯ ФАКТОРИАЛОВ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

же сделал предположение о том, что метод бинарных вставок оптимален и в общем случае. Несколько лет спустя Штейнгауз сообщил [Calcutta Math. Soc. Golden Jubilee Commemoration 2 (1959), 323-327], что двое его коллег, С. Трибула (S. Trybula) и Чжен Пинг (Р. Czen), "недавно" опровергли его предположение и нашли значения S{n) при п < 11. Вероятно, Трибула и Чжен Пинг независимо пришли к сортировке посредством вставок и слияния, о чем вскоре появилась публикация Ford, Johnson, АММ 66 (1959), 387-389.

После открытия сортировки посредством вставок и слияния первым неизвестным значением функции 5(п) оставалось 5(12). Из табл. 1 видно, что число 12! довольно близко к 2®, поэтому существование 29-шаговой процедуры сортировки 12 элементов весьма маловероятно. Для решения этого вопроса Марком Уэлсом (Mark Wells) был предпринят продолжительный вычислительный эксперимент (продолжавшийся на компьютере Maniac П около 60 ч), который показал, что 5(12) = 30 [Ргос. IFIP Congress 65 2 (1965), 497-498]. Итак, процедура вставок и слияний оказывается оптимальной и при п - 12.

*Более глубокий анализ. Чтобы более тщательно исследовать функцию 5(п), внимательно изучим диаграммы частичного упорядочения, подобные (5). Полученные после нескольких сравнений сведения можно представить в виде ориентированного графа. Этот граф в силу транзитивности отношения "<" не содержит циклов. Следовательно, его всегда можно изобразить таким образом, чтобы все дуги были ориентированы слева направо; поэтому удобнее удалить из диаграммы стрелки. В результате диаграмма (5) преобразуется в

и и

Пусть G - такой ориентированный граф; обозначим через T{G) число перестановок, согласующихся с G, т. е. число способов разметки вершин графа G целыми числами {1,2,..., п} так, чтобы число в вершине х было меньше числа в вершине ?/, если дуга х у принадлежит G. Вот пример перестановки, согласующейся с (21): а = 1, b = 4, с = 2, d = 5, е = 3. Мы проанализирова)ш функцию T{G) для различных G в разделе 5.1.4, в котором было отмечено, что T{G) есть число вариантов топологической сортировки графа G.

Пусть G - граф из п элементов, который можно получить поале к сравнений; определим эффективность графа G функцией

EiG) = (22)

(Эта идея принадлежит Фрэнку Хвангу (Frank Hwang) и Шень Линю (Shen Lin).) Строго говоря, эффективность не есть функция лишь самого графа G - она зависит от того пути, которы.м мы пришли к G в процессе сортировки, однако для простоты закроем глаза на эту маленькую неточность. Выполнив еще одно сравнение элементов i и j, получим два графа (Gi и G2): один - для случая Ki < Kj, а другой - для случая Ki > Kj. Ясно, что

r(G) = r(Gi) + r(G2).

Если r(Gi) > TiG-z), то имеем

T{G) < 2T{Gi), п\ E{G)T{G)

E{Gi) 2fc+ir(Gi) 2r(Gi)

< EiG). (23)

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

Заметим, что если G совсем не содержит дуг, то fc = О и T{G) = п\, т. е. начальная эффективность равна 1. Если же граф G представляет окончательный результат сортировки, то он выглядит, как отрезок прямой, и T{G) = 1. Так, например, если нам нужно построить процедуру сортировки пяти элементов за семь или менее сравнений, то необходимо получить линейный граф --• эффективность которого равна 5\/{2 х 1) = 120/128 = 15/16. Отсюда следует, что все графы, возникающие в процессе сортировки, должны иметь эффективность

> j; если бы появился какой-нибудь граф меньшей эффективности, то, по крайней мере, один из его потомков тоже имел бы меньшую эффективность и мы бы, в конце концов, пришли к линейному графу с эффективностью < jf. В общем случае это рассуждение показывает, что все графы, соответствующие узлам дерева для некоторой процедуры сортировки п элементов, должны иметь эффективность

> п!/2, где I - число уровней в дереве (не считая внешних узлов). Это еще один способ доказательства неравенства 5(п) > "lgn!], хотя такое рассуждение на самом деле не сильно отличается от приведенного выше.

Граф (21) имеет эффективность 1, поскольку T{G) = 15 и граф G был получен за три сравнения. Чтобы выяснить, какие вершины должны участвовать в следующем сравнении, можно построить матрицу сравнений

а Ь с d е

а /О 15 10 15 11\

6 О О 5 15 7

C{G) = с 5 10 О 15 9 , (24)

d О О О О 3

е \4 8 6 12 О/

где Cij есть T{Gi) для графа G\ Т (Gi), полученного путем добавления дуги г -> j в G. Если мы, например, сравним Кс с Kg, то 15 перестановок, согласующихся с G, распадутся на две группы: Сес = б, в которых Kg < Кс, и Ссе = 9, в которых Кс < Kg. Последний граф имел бы эффективность 15/(2 х 9) = < у, так что это сравнение не может привести к процедуре сортировки из семи шагов. Если мы хотим сохранить эффективность > jf, то следующим сравнением обязано быть

Концепция эффективности особенно полезна при рассмотрении связных компонентов графов. Возьмем, например, граф

он состоит из двух компонентов:

G= / и G" =

с / 9

В этих компонентах ни одна дуга не соединяет G с G"; следовательно, он был образован путем нескольких сравнений вершин только G и независимо нескольких сравнений вершин только G". В общем случае предположим, что граф G = G ®G" не содержит дуг, связывающих G и G", где G и G" имеют соответственно п и п" вершин; легко видеть, что

Г((?) r(G)r(G"), (25)

поскольку каждая перестановка, согласующаяся с G, получается в результате выбора п элементов, которые считаются принадлежащими графу и последующего составления независимых перестановок, согласующихся с G и G". Пусть внутри G выполнено fc сравнений, а внутри G" - соответственно fc" сравнений; получаем основной результат

E{G) - k+k"T{G) ~ Wnp) 2>"T{G) -

показьшающий, что между- эффективностью графа и эффективностью его компонентов существует простая связь. Поэтому мы можем ограничить наше рассмотрение графами, имеющими только один компонент.