Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 39
Текст из файла (страница 39)
Время выполнения сортировки по этому методу пропорционально Х!ой%; будем называть его выбором иэ дерева. Выбор из дерева. Принципы сортировки посредством выбора из дерева будет легче понять, если воспользоваться аналогией с типичным "турниром с выбываннем'! Рассмотрим, например, результаты соревнования по настольному теннису, показанные на рис. 22. В первом туре Ким побеждает Сэнди, а Крис побеждает Лу; затем в следующем туре Крис выигрывает у Кима и т. д. Крис Рис.
22. Турнир по настольному теннису. На рис. 22 показано, что Крис — чемпион среди восьми участников. Для того чтобы определить это„потребовалось 8 — 1 = 7 матчей (т. е. сравнений). Пат вовсе необязательно бут вторым по силе игроком; любой из спортсменов, у которых выиграл Крис, включая даже проигравшего в первом туре Лу, может оказаться вторым цо силе. Второго игрока можно определить, заставив Лу сыграть с Кимом, а победителя этого матча — с Патом. Всего двух дополнительных матчей достаточно для определения второго по силе игрока, исходя из соотношения сил, которое было учтено на основании предыдущих игр.
Вообще говоря, можно "вывести из турнира" игрока, находящегося в корне дерева, заменить его заведомо слабейшим новичком и повторить розыгрыш. Включение этого слабака приведет к тому, что первоначально второй по силе участник станет теперь наилучшим н именно он окажется в корне, если вновь вычислить победителей в верхних уровнях дерева. Для этого нужно изменить лишь один путь в дереве, так что для выбора следующего по силе игрока необходимо менее ()8 Аг) дополнительных сравнений. Суммарное время выполнения такой сортировки посредством выбора примерно пропорционально Х!об Х, как и утверждалось выше.
На рнс. 23 показано, как применить эту схему к нашим 16 числам. Заметим, что для того, чтобы знать, куда вставлять следующий элемент — со, необходимо помнить, где находился ключ, оказавшийся в корне. Поэтому узлы разветвления в действительности содержат указатели или индексы, описывающие позицию ключа, а не сам ключ. Отсюда следует, что необходима память для Ю исходных записей, Х вЂ” 1 указателей и Ю выводимых записей. (Разумеется, если вывод идет на ленту нли диск„то не нужно сохранять выводимые записи в оперативной памяти.) Чтобы оценить те замечательные усовершенствования, которые мы собираемся обсудить, в этом месте рекомендуется прервать чтение и выполнить упр. 10.
Не усвоив базовые принципы рассматриваемого метода, нельзя двигаться дальше. Одна из модификаций выбора из дерева, введенная, по существу, К. Э. Айверсоном (К. Е. 1хегзоп) [А Ргойгашш1пй 1апйпаяе (1ч11еу, 1962), 223-227], устраняет необходимость указателей. Достигается это тем, что мы "заглядываем вперед"". когда победитель матча на нижнем уровне поднимается вверх, на нижнем уровне его сразу же можно заменить элементом -оо; когда же победитель перемещается вверх с одного разветвления на другое, его можно заменить игроком, который, в конце копцов, все равно должен подняться на его прежнее место (а именно — наиболыпим из двух ключей, расположенных под ним).
Повторяя эту операцию как можно чаще, придем от рис. 23, (а) к рис. 24. Коль скоро дерево построено таким образом, можно продолжать сортировку "нисходящим", а не "восходящим" методом, показанным на рис. 23: выводится 908 76$ /~ /~ /~ П /~ П /~ Л 503 087 $12 061 908 170 897 275 653 426 И4 $09 612 67Т 76$ Т03 (а) Исходная ковфягурацяя l~ П /~ /~ /~ /~ /~ /~ П $03 067 512 06! -оо 170 897 27$ 653 426 1$4 $09 612 677 765 703 (Ь) Ключ 908 заменен значением -оо, а вторая по старвяяссву завесь переминается в корень У~ l~ l~ /~ П /~ /~ /~ й О й 503 087 $12 061 -со 170 -оо 275 -со 426 И4 509 -сю -оо -оо -со (с) КонФягураняя после вывода 90$, 89Т, 76$, 703, 677, 653 я 612 Рис. 23. Пример сортировки посредством выбора.
l~,l~ l~ /~ /~ /~ /~ /~ /~ П Л -со 087 -оо -ао -оо -оо -оо -сю -сю -оо 154 -сю 672 — оо — оо — сю Рис, 24. Принцип Питера, примененный к сортировке. Каждый поднимается на свой уровень компетенции в иерархии. злемент, находящийся в корне, перемещается вверх иаибольшвй из его потомков, перемещается вверх наибольший из потомков последнего и т.
д. Процесс начинает походить ие столько иа турнир по настольному теннису, сколько на систему выдвижений в корпорации. Читатель должен, уяснить, что у нисходящего метода есть важное достоинство — он позволяет избежать лишних сравиепий — оо с — оо. (Пользуясь восходящим методом, мы на более поздних стадиях сортировки всюду натыкаемся на — оо, а при нисходящем методе можно на каждой стадии заканчивать преобразование дерева сразу же после занесения — оо.) На рис. 23 и 24 изображены полные бинарные деревья с 16 концевыми узлами (см.
раздел 2.3.4.5). Такие деревья удобно хранить в последовательных ячейках памяти, как показано на рис. 25. Заметим, что родителем узла номер и является узел (й/2), а его потомкамв являются узлы 2й и 2л+ 1, Отсюда вытекает еще одно преимущество нисходящего метода — зачастую значительно проще продвигаться вниз от узла й к узлам 2й и 2й+ 1, чем вверх от узла й к узлам ЙЮ 1 и (й/2). (Здесь через Й Ю 1 обозначено число л + 1 или Й вЂ” 1 в зависимости от того, каким является Й: четным или нечетным.) Рмс. 2$.
Последовательное распределение памяти для пслиого бинарного дерева. До сих пор в примерах выбора из дерева в той или иной мере предполагвлосзч что й" есть степень 2. В действительности можно работать с произвольным значением Ю, так как полное бипарпое дерево с Ф концевыми узлами нетрудно построить для любого Х Мы подошли теперь к основному вопросу: нельзя ли в нисходящем методе обойтись совсем без — сю7 Не правда ли, было бы чудесно„если бы всю существенную информацию, которая представлена на рис. 24, удалось расположить в ячейках от 1 до 16 полного биварного дерева безо всяких бесполезных "дыр", содержащих -па 7 Поразмыслив, можно прийти к выводу, что зта цель в действительности достижима, причем не только исключается -со, но и появляется возможность сортировать записи в пределах того же фрагмента памяти без дополнительной области для накопления резульштв.
Это позволяет получить еще один важный алгоритм сортировки — пирамидальную сортировку (оеар-зогФ). Его автор — Дж. У. Дж. Уильямс (Л. %. Л. %1П1ашя) (САСМ 7 (1964), 347-348). Пирамидальная сортировка, Будем называть массив ключей К»,Кт„...,Ки пирамидон, если К( !т! >К при1< [т/2] <у<К. (3) В этом случае К» > Кз, К1 > Кэ Кт > К4 и т. д. Именно это условие выполняется на рис. 24. Из него следует; в частности, чта наибольший ключ оказывается "на вершине пирамиды": К» = шах(К„Кз, . °,Кл), (4) Если как-нибудь преобразовать произвольный исходный массив в пирамиду, то для получения эффективного алгоритма сортировки можно воспользоваться "'нисходя- щей'" процедурой выбора, подобной той, которая описана выше.
Эффективный подход к построению пирамиды предложил Р. У. Флойд [Н. %. Г)оу»), САСМ Т (1964), 701]. Предположим, удалось расположить массив таким образом, что КПуэ! > Кэ пРи ! < [//2] </ < Ж, (5) где ! — некоторое числа > 1. (В исходном массиве это условие выполняется автоматически для ! = [Ю/2], поскольку ни один индексу не удовлетворяет условию [!»»/2] < [»/2] < у < 5!.) Нетрудно понять, как, изменяя лишь полдерева с корнем в узле 1, преобразовать массив, чтобы распространить неравенства (5) и на случай, когда ! = [у/2]. Следовательно, можно уменьшать ! на единицу„пака, в конце концов, не будет достигнуто условие (3).
Эти идеи Уильямса и Флойда приводят к изящному алгоритму, который заслуживает пристального внимания (рис. 26). Алгоритм Н (Пирамидальнвл сора»ировка). Записи В»,...,Ви перекомпанавы- ваются в пределах того же фрагмента памяти; после завершения сортировки их ключи будут упорядочены следующим образом: К» « . Ки Сначала массив перестраивается в пирамиду, а затем вершина пирамиды многократно исключается и записывается на свое окончательное место. Предполшвется, что Х > 2.
Н1. [Начальная установка.] Установить ! [Ю/2] + 1, г»- Ю. НЗ. [Уменьшить ! или г.] Если ! > 1, установить ! +- ! — 1, В»- Ва К» — Кь (Если ! > 1, значит, происходит преобразование исходного массива в пирамиду; если же ! = 1, значит, ключи К1 Кт...К, уже образуют пирамиду.) В противном случае установить В»- В„, К ~- К„, В, +- В1 и г»- г — 1; если в результате оказалось, что г = 1, установить В1 +- В и завершить выполнение алгоритма.
НЗ. [Приготовиться к "протаскиванию".] Установить у»- !. (К этому моменту К1»!э! > К» при ! < [к/2] < !г < г, (6) а запись В», г < к < /»г, занимает свое окончательное места. Шаги НЗ-Н8 называются алгорипьмом "прап»аскнввнпл"'; выполняемые при этом операции эквивалентны установке В!»- В с последующей перекомпановкой записей Вп..., В, таким образом, чтобы условие (6) выполнялось и при ! = [й/2].) Н4. [Продвинуться вниз.] Установить ! +- » и у»- 21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
