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