Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 16
Текст из файла (страница 16)
-,р различны, если после применения алгоритма 1 последовательно к рм рэ,...,р~, начиная с пустой диаграммы Р, оказывается, что р; = Рмь (Напомним, что алгоритм 1 всегда вставляет данный элемент в 1-ю строку; ) легко видеть., что (6ь,р;) принадлежит классу 1 тогда и только тогда, когда р; имеет 1 — 1 инверсий, т. е. тогда и только тогда, когда р, = пнп(рмрз,...,р;)— "левосторонний минимум". Если в массиве (16) вычеркнуть столбцы класса 1, то получится двухстрочный массне (17) Пусть также р; есть элемент х, который удаляется пз Р по алгоритму 0 с использованием значений э н 8, таких, что 9м - -Е, причем 4 = и,..., 2, 1 (именно в таком порядке). Например, если прпменить зто построение к диаграмме (13) и производить вычисления, обратные (12), до тех пор, пока Р не исчерпается, то получится массив (г э э э э).
Поскольку алгоритмы 1 я 0 взаимно обратны, взаимно обратны и описанные здесь два построения; таким образом, требуемое взаимно однозначное соответствие установлено. $ Соответствие, определенное в доказательстве теоремы А, обладаег множеством поразительных свойств, и теперь мы приступим к выводу некоторых из ннх.
Убедительная просьба к читателю: прежде чем двигаться дальше, выполните упр. 1, чтобы освоить методику построений. Как галька элемент вытеснен из строки 1 в строку 2, он уже не вышлет на строку 1; кроме того, строки 2, 3, ... строятся из последовательности "вытесненных" элементов так же, квк строки 1, 2, ... строятся из исходной перестановки. Это наводит на мысль о том, что на построение в теореме А можно взглянуть иначе, обращая внимание лишь на первые строки Р и Я. Напрпмер, перестановка (' э ээ э э) вызывает следующие действия над строкой 1 (ср. с (12)): 1: Вставить 7, присвоить Яы <- 1. 3: Вставить 2, вытеснить 7.
5: Вставить 9, присвоить Я|э <- 5. (14) 6: Вставить 5, вытеснить 9. 8: Вставить 3, вытеснить 5. Таким образом, первая строка Р— зто 2 3, а первая строка Я вЂ” зто 1 5. Кроме того, остальные строки Р и Я составляют диаграммы, совтветствующне "вытесненному" двухстрочному массиву такой, что пара (9, Р) принадлежит классу 1 относителыю (17) тогда и только тогда, когда она принадлежит классу г+ 1 относительна массива (16).
Операция перехода от (16) к (17) соответствует удалению крайней слева позиции строки 1. Это дает систематический способ определенкя классов. Например, в перестановке (т з э ь з ) 1зэаэ левосторонними минимумами являются элементы 7 и 2, так что класс 1 — это ((1,7), (3,2)); в оставшемся массиве (~ е з) все элементы минимальны, так что класс 2 — это ((5,9), (6,5), (8,3)). В "'вытесненном" массиве (15) класс 1 — это ((3, 7), (8, 5)), а класс 2 — ((6, 9)). Для любого фиксированного 1 элементы класса 1 можно так пометить (йп Рп )~ ~ (йц, Рц ) чтобы выполнялись неравенства йп с%.> ('' 'сЧц~ (18) Рп > Рз » ' ' Рм ~ поскольку в процессе выполнения алгоритма вставки позиция диаграммы Рм принимает убываюшую последовательность значений Р;„..., р;„.
В конце построения Рм = Рц Юм = В (19) а вытесненный двухстрочный массив, которым определяются строки 2, 3, ... диаграмм Р н 9, содержит столбцы я, в, " в, 1 (20) и другие столбцы, аналогичным образом полученные из других классов. Эти рассуждения приводят нас к простому методу вычисления Р и Я вручную (см. упр. 3), а также предоставляют средства для доказательства одного весьма неожиданного рк~ультата. Теорема В. Если в построенип нз теоремы А перестановка (', '.;) соответствует диаграмме (Р,®, то обратная ей перестановка соответствует дпаграмме Я, Р).
Это довольно удивительный факт, потому что в теореме А дяаграммы Р и Сг формируются совершенно разными способами и обратная перестановка получается в результате весьма причудливой перетасовки столбцов двухстрочного массива. Доквзательсшеа. Предположим, имеется двухстрочный массив (16); поменяв местами его строки и рассортировав столбцы так, чтобы элементы новой верхней строки расположились в порядке неубывания, получим "обратный" массив Р1 Рз ° ° Р~ 91 (М, а .. ж) Рз Ра~ Р1 С Рз ( ''' < 3~в~ (21) йз . Я / д'„д',...,д„' различны.
Покажем, что зта операция соответствует взаимной замене Р и г,г в построении нз теоремы А. В упр. 2 наши замечанкя об определении классов переформулированы таким образом, что класс, к которому относится пара (опр;), не зависит от того факта, что элементы дм дэ,..., дч расположены в порядке возрастания. Поскольку результирующие условия симметричны относительно й и р, операция (21) не нарушает структуру классов; если (д,р) принадлежит классу Г относительно (16), то (Р,е) принадлежит классу Г относительно (21).
Поэтому, если разместить элементы последнего класса 1 так, чтобы Рц «'''Р»» <Рг», 4»» » ' ' ' В» > %~1 (22) то по аналогии с (18) получим (23) й»» йь, как в (19), а столбцы (24) войдут в вытесненный массив, как в (20). Следовательно, первые строки Р н 1,Г меняются местами. Ереме того, вытесненный двухстрочный массив для (21) является обратным по отношению к вытесненному двухстрочному массиву для (16), так что доказательство завершается применением ицлукцни по числу строк в диаграмме, $ Следствие, Колггчество диаграмм, которые можно сформировать из элементов (1, 2,..., и), равно количеству инаолюшгй множества (1,2,..., и).
ДЪкаэатааьстео, Если гг — ннволюция, соответствующая паре диаграмм (РД), то гг = я соответствует паре (4г, Р). Следовательно, Р = 9, Обратно, если ив калан-либо перестановка, соответствующая паре (Р, Р), то я тоже соответствует паре (Р, Р); отсюда я = я . Таким образом, существует взаимно однозначное соответствие между ннволюциями э.
и диаграммой Р. 3 Ясно, что элемент в левом верхнем углу диаграммы всегда наименьший, Это наводит на мысль о возможном способе сортировки множества чисел, Сначала мовьно составить из них диаграмму, многократно применяя алгоритм 1, и в результате наименьший элемент окажется в углу, Затем этот наименьший элемент удаляется, а остальные элементы переразмещаются так, чтобы образовалась другая диаграмма; потом удаляется новый минимальный элемент и т. д.
Поэтому давайте посмотрим, что происходит, когда мы удаляем угловой элемент из диаграммы После удаления 1 на освободившееся место необходима поставить 2. Затем можно поднять 4 на место 2, однако 10 нельзя поднять на место 4; на зто место можно подвинуть 9, а потом 12 — на место 9. В общем случае приходим к следующей процедуре. Алгоритм Я [Удаление разового элемента). Этот алгоритм удаляет элемент из левого верхнего угла диаграммы Р и перемещает остальные элементы так, чтобы сохранились свойства диаграммы. Далее используются те же обозначения, что и в алгоритмах 1 и О.
Я1. [Начальная установка.) Присвоить г +- 1, э <- 1. Я2. [Выполнено?[ Если Р„, = оо, то процесс завершен. ЯЗ. [Сравнить.] Если Р „+,~, < Р~,+ц, то перейти к шагу Бб, (Сравниваем элемен- ты справа и снпзу от свободного места и передвигаем меньший из них.) Я4. [Сдвиг влево.[ Присвоить Р„, <- Р„<, и, э +- э + 1 н вернуться к шагу БЗ. Яб. [Сдвиг вверх.) Присвоять Р„, ~- Р<,+ц„г +- г + 1 и вернуться к шагу Б2. ! Легко доказать, что после удаления с помощью алгоритма Б углового элемента Р по-прежнему является диаграммой [см. упр.
1О). Таким образом, применяя алгоритм Б до тех пор, пока Р не исчерпается, можно прочитать его элементы в порядке возрастания. К сожалению, этот алгоритм сортировки оказывается не столь эффективным, как другие алгоритмы„которые нам еще предстоит рассмотреть. Минимальное время его работы пропорционально п~ ~; аналогичные алгоритмы, использующие вместо диаграмм деревья, затрачивают время порядка и 1ой и. Хотя алгоритм Б в приложении к сортировке н не отличается особой эффективностью, он обладает некоторыми очень интереснымн свойствами. Теорема С (М.
П. Шуценберже (М. Р. Яспцглепбегйег)). Если Р— диаграмма, построенная, как в теореме А, нз перестановки а~ аз, а„, л еглп а, = ппп[амаз,...,а„), то алгоритм Б преобразует Р в диаграмму, соответствующую перестановке а~... а; ~ а~+~" ач Доказательство. См. упр.
13. ! Давайте после применения алгоритма Б поместим на вновь освобцдившееся место Р„удаленный элемент, ио отобразим его курсивом, указав таким образом, что на самом деле элемент не является частью диаграммы. Применив, например, эту процедуру к диаграмме [25), мы получим а выполнив такую же процедуру еще два раза, получим Продолжая до тех пор, пока все элементы не будут удалены, получим конфигурацию имеющую ту же форму, что и исходная диаграмма (25). Зту конфигурацию можно назвать деойстнееииой диаграммой, потому что она похожа на диаграмму с той лишь разницей, что применяется "двойственное отношение порядка" (> и < поменялись ролями). Обозначим двойственную диаграмму, полученную из Р таким способом, через Рз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
