AOP_Tom3 (1021738)
Текст из файла
-" Введение е Ответы к упражнениям ° Приложение А. Таблицы значений некоторых констант ° Приложение Б. Основные обозначения е Глава 5. а 5.1 о 5.2 с 5.3 " 5.4 :" 5.5 ° Глава 6. о 6.1 —. 6,2 . 6.3 а 6.4 : 6.5 СОРТИРОВКА Комбинаторные свойства перестановок Внутренняя сортировка Оптимальная сортировка Внешняя сортировка Резюме.
История и библиограФия Поиск Последовательный поиск Поиск путем сравнения ключей Цифровой поиск Хеширование Выборка по вторичным ключам 5.3. ОПТИМАЛЬНАЯ СОРТИРОВКА ТепеРЬ, КОГДА МЫ проанализировали множество методов внутренней сортировки, пришло время обратиться к более общему вопросу: какой мепюд внутренней сортпировки наилучший". Существует ли такой верхний предел скорости сортировки, которого бы не мог достичь ни один программист, как бы искусен он ни был? Разумеется, не сущестпвует наилучшего возможного способа сортировки; мы должны точно определить, что понимать под словом "наилучший", но не существует наилучшего возможного способа определения слова "наилучший' ! Аналогичную проблему, связанную с оптимальностью алгоритмов, мы обсуждали в разделах 4.3.3, 4.6.3 и 4.6.4, в которых рассматривались умножение с повышенной точностью и вычисление полиномов.
В каждом случае, для того чтобы задача была поставлена в терминах конкретных математических структур, необходимо было сформулировать довольно простое определение "наилучшего из возможных" алгоритма. И в каждом случае перед нами вставали интереснейшие проблемы, настолько сложные, что они до сих пор полностью не решены. Так же обстоит дело и с сортировкой: бьщи получены некоторые интересные результаты, но осталось еще много интригующих вопросов, на которые до сих пор нет ответов. Изучение внутреннего механизма методов сортировки обычно было направлено на минимизацию числа сравнений ключей при сортировке и элементов или слиянии т элементов с и элементами, илн выборе 1-го наибольшего элемента из неупорядоченного набора т1 элементов. В разделах 5.3.1-5.3.3 эти вопросы обсуждаются для общего случая; в разделе 5.3.4 рассматриваются аналогичные вопросы с интересным ограничением: схема (структура) сравнений должна быть, по сути, заранее фиксированной.
Другие интересные теоретические вопросы, связанные с оптимальной сортировкой, можно найти в упражнениях к разделу 5.3.4 и в разделах 5.4.4, 5.4.8 и 5.4.9, в которых анализируется внешняя сортировка. Как только появится аналитическая машина, она, безусловно, опрелслит дальнейший путь оазвития науки. Всякий оаз, когда с ее помощью будет найден какой-либо оезультат, возникнет вопрос: "Существует ли метод вычислений, котооым можно получить на этой машине тот же результат, но затратив минимум времени?: — чАРльз БЭББидук Паба) 5.3.1.
Сортировка с минимальным числом сравнений Очевидно, минимальное число сравнений ключей, необходимое для сортировки и элементов, равно нулю, поскольку, как мы видели, существуют методы поразрядной сортировки, в которых сравнения вообще не выполняются. В самом деле, можно разработать й1Х-программы, способные сортировать н, тем не менее, .не содержащие ни одной команды условного перехода! (См.
упр. 5 — 8 в начале этой главы.) Мы также встречались с несколькими методами сортировки, которые, по сути, были основаны на сравнении ключей, но время выполнения которых на деле определялось другими факторамн, такими как перезапись данных, вспомогательные операции и т.
д. Поэтому ясно, что подсчет числа сравнений — — не единственный способ измерения эффективности метода сортировки. Однако в любом случае небеэынтерес- но провести тщательное исследование числа сравнений, поскольку теоретический анализ злого вопроса позволит нам Гюлее глубоко проникнуть во внутреннюю природу процессов сортировки, а также поможет отточить мастерство для решения задач, более близких к практике, которые могут возникнуть перед нами в будущем. Исключим из рассмотрения метод поразрядной сортировки, в котором совсем не выполняется сравнений. и ограничимся обсуждением методов, основанных только на абстрактном линейном отношении порядка '<" между ключами, рассмотренном в начале этой главы.
Для простоты мы также ограничимся случаем различных кмючей, а зто значит, что при любом сравнении ключей К, и К. возможны лишь два исхода: либо К; < К, либо К, > К . (Распространение результатов такого анализа на общий случай, когда допускаются равные ключи, приводится в упр. 3-12.) Ограничения на время выполнении в худшем случае рассматриваются в работах Ггес1шап, %'|11агс1, Х Сотрнсег и луза Ясй 47 (1993)„424-436, Веп-Ашгаш, Оа)11, Х Сошр. Яузк Зп'.
54 (1997), 345 -370 и Тпогнр, ЯОПА 9 (1998), 550-555. Возможны и другие эквивалентные варианты постановки задачи сортировки посредством сравнений, Если есть н грузов и весы с двумя чашами, то каково минимальное число взвешиваний, необходимое для того, чтобы расположить грузы по порядку в соответствии с весом, если в каждой чаше весов помещается только один груз? Или же, если в некотором турнире участвуют п игроков, то каково наименьшее число парных встреч, достаточное для того, чтобы распределить места между соревнующимися в предположении, что силы игроков можно линейно упорядочить (ничейные результаты не допускаются).
Методы сортировки и, элементов, удовле'гворяющие указанным ограничениям, можно представить с помощью структуры расширенного бинарного дерева, такого, когорое показано на рис. 34. Каждый внугнренний узел (изображенный в виде кРУжочка) содеРжит два индекса ьыз" и означает сРавнение ключей К; и Кэ. Левое поддерево этого узла соответствует пот зедующим сравнениям, которые необходимо выполнить. если К, < К, а правое поддерево — — тем дейгтвиям, которые необходимо предпринять, если К, > К,. Каждый внешний узел дерева (изображенный в виде прямоутольника) содержит перестановку а~ аз...
а„множества 11, 2,..., п), а это обозначает, что было установлено упорядочение К, <К.,«. К,„. 1Если взглянуть на путь от корня к этому внешнему узлу, то каждое из п — 1 соотношений К„, < К..., где 1 < 1 < и, -. результат некоторого сравнения а,:и; г или щ.>~..а; на этом пути.) Так, на рис. 34 представлен метод сортировки, суть которого состоит в том, чтобы сначала сравнять Кг с Ке: если К~ > Кьч то продолжать (двигаясь по правому поддереву) сравнивать К» с Кз, а затем, ешш К < Кз, сравнить Кг с Кз.
наконец, если К~ > Кз, становится ясно, что Кз < Кз < Км Реальный алгоритм сортировки будет также перезаписывать ключи в массиве, но нас интересуют только сравнения, поэтому мы игнорируем все перезаписи данных. При сравнении К, с К в этом дереве всегда имеются в виду исходные ключи К; н Кч а не те ключи, которые могли занять 1- н у-ю позиции в массиве в результате перемещения записей. Возможны и избыточные сравнения; например, на рис. 35 нет необходимости сравнивать 3: 1, поскольку из неравенств К~ < Кз и Кз < Кз следует Кг < Кз. Ни- Уровень О Уровень 1 Уровень 3 Уровень 3 Рис.
34. Дерево сравнений для сортировки трех элементов. Рис. Зб. Пример избыточного сравнения. какая перестановка не может соответствовать левому поддереву узла 3:1 на рис. 35, так что эта часть алгоритма никогда не будет выполняться! Поскольку нас интересует минимальное число сравнений, можно считать, что избыточные сравнения не выполня1отся. С этого момента мы будем иметь дело со структурой расширенного бинарного дерева, в котором каждому внешнему узлу соответствует некоторая перестановка.
Все перестановки исходных ключей возможны, н каждая перестановка определяет единственный путь от корня к внешнему узлу; отсюда вытекает, что в дереве сравнений для сортировки п элементов без избыточных сравнений имеется ровно п1 внешних узлов. Оптимизация в наихудшем случае. Первая естественным образом возникающая задача — найти деревья сравнений, минимизирующие максимальное число выполняемых сравнений. (Позже мы рассмотрим среднее число сравнений.) Пусть Я(п) — минимальное число сравнений, достаточное для сортировки п элементов.
Если все внутренние узлы в дереве сравнений располагаютсн на уровнях < к, то очевидно, что в дереве не может быль более 21 внешних узлов. Следовательно, полагая к = о'(п), имеем п! < 2~1"1 Поскольку о'(п) — целое число, можно записать эту формулу иначе, получив нижнюю оценку: 8(п) > [1Кь111. (1) Заметим, что по формуле Стирлинга [оп)) = п1кп — п/1п2+ -'оп+ 0(1), следовательно, необходимо выполнить около п !8 и сравнений.
Соотношение (1) часто называют теоретико-информационной нижней оценкой, поскольку специалист в области теории информации сказал бы, что в процессе сортировки проверяется !8п! "бнт информации": каждое сравнение дает не более одного бита информации. Такие деревья, как на рис. 34, называют также "вопросниками" (циевт!оппа1гев); их математические свойства исследованы в книге С!апг!е Р!саге!, ТЬеоПе с(еэ Янезе!апов!гее (Рапв: Сап!а!ег-Ч!!!агв, 1965). Из всех рассмотренных нами методов сортировки трп метода требуют меньше всего сравнений: бинарные вставки (см.
раздел 5.2.1), выбор из дерева (см. раздел 5,2.3) н простое двухпутевое слияние., описанное в алгоритме 5.2.4Ь). Нетрудно видеть, что максимальное число сравнений для метода бинарных вставок равно и В(п) = ЕГ!8)е1 = п(!Кп) — 2!!к"! + 1 э=1 (3) (см. упр. 1.2.4-42), а максимальное число сравнений для двухпутевого слияния определено в упр. 5.2.4-14. Оказывается (см.
раздел 5.3.3), что для метода выбора из дерева верхняя оценка числа сравнений либо такая же, как для метода бинарных вставок, либо такая же, как для двухпутевого слияния, в зависимости от вида дерева. Во всех трех случаях имеем асимптотическое значение и!8п; объединяя верхнюю и нижнюю оценки для Я(п), получим !пп = 1. Я(п) «->се и!8п (4) и. = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 !'!8п!"! = 0 1 3 5 7 10 13 16 19 22 26 29 ЗЗ 37 41 45 49 В(п) = 0 1 3 5 8 11 14 17 21 25 29 ЗЗ 37 41 45 49 54 Ь(п) = 0 1 3 5 9 11 14 17 25 27 ЗО ЗЗ 38 41 45 49 65 Здесь В(п) и Цп) относятся соответственна к методам бинарных вставок и слияния списков. Можно показать, что В(п) < А(п) при любом п (см.
упр. 2). Как видно из приведенной выше таблицы, Я(4) = 5, но 5(5) может равняться либо 7, либо 8. В результате снова приходим к задаче, поставленной в начале раздела 5.2. Каков наилучший способ сортировки пяти элементов? Возможна ли сортировка пяти элементов при помощи всего семи сравнений? Такая сортировка возможна, но сам способ найти не так просто. Начинаем так же, как при сортировке четырех элементов посредством слияний, сравнивая сначала К~.Кэ, затеи — — Кэ.
Км а затем — нанбольшне элементы обеих пар. Эти сравнения порождают конфигурацию, которую можно изобразить диаграммой (5) а е е Таким образом, мы получили приближенную формулу для Б(п), однако желательно иметь более точную оценку. В сведующей таблице приведены значении верхней и нижней границ при малых и. показывающей, что а < 6 < 41 и с < 41. (Для представления известных отношений порядка между элементами удобно воспользоваться ориентированными графами, такими, что х считается меньше у тогда и только тогда, когда на графе есть путь от х к Ьс) Теперь вставляем пятый элемент Кз = е в соответствующее место среди (п, 6, 41); для этого требуются всего два сравнения, поскольку можно сравнить его сначала с Ь, а затем — с а или 44.
Таким образом, остается один из четырех возможных вариантов а 0 а 41 0 и в каждом случае достаточно еще двух сравнений, чтобы вставить с в цепочку остальных элементов, меньших 44. Такой способ сортировки пяти элементов впервые обнаружил Г. Б. Демут (Н. В. Ве!пиН!) [Р)4. П. 6)тезтз, Бзапзог41 Пп!гегз!Ьу (1956), 41 43). Сортировка посредством вставок и слияния. Изящное обобщение изложенного выше метода принадлежит Лестеру Форду (мл.) (Везсег Го!41, Яг.) и Селмеру М.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
