Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 49
Текст из файла (страница 49)
Сложите эти две стопки и поверните их лицевой стороной вверх. Колода будет рассортирована. Докажите, что приведенную выше последовательность карт нельзя рассортировать в порядке йбмеамил К 2 1 ... 2 А от верхней карты к нижней за два просмотра, даже если разрешено раскладывать карты в три стопки. (Сдавать карты нужно всегда сверху колоды, поворачивая их рубашкой вверх. На рисунке верхняя карта колоды изображена справа, а нижняя — слева.) 1Ь, )Мйб) Рассмотрите задачу из упр. 14 для случая, когда карты раздаютса лицевой стороной вверх, а не вниз. Таким образом, один просмотр можно потратить на преобразование возрастающего порядка в убывающий. Сколько нужно просмотров? э 16. (26) Разработайте алгоритм сортировки строк оп ..., о, состоящих из тп букв в лексикографическом порядке. Суммарное время выполнения этого. алгоритма должно быть порядка О(гп+ и+ Х), где М = )о.(+. + )о ( — суммарная длина всех строк, 17.
)15) Почему в двухуровневом методе сортировки, предложенном Тамминеном (см. теорему Т), метод, аналогичный алгоритму Мак-Ларена, используется на втором и не используется на первом уровне? 1й. (НАзЯ6) ДоквжитетеоремуТ. Указание. Сначалапокажите,чтоалгоритм Мак-Ларена действительно выполняет в среднем О(В1т') операций, если его применять по отношению к независимым случайным ключам, для которых функция плотности вероятностей удовлетворяет условию г(к) < В при 0 < л С 1. Для сортировки корней и слов нам понадобится 1100 ящиков и лотков для форм, — ДМСОРДйк В. ВИГРАМ (ВЕОЙВЕ Ч. ФЛВйАМ) (1643) 5.3.
ОПТИМАЛЬНАЯ СОРТИРОВКА Ткпкгь, когда мы проанализировали множество методов внутренней сортировки, пришло время обратиться к более общему вопросу: какой метпод енутпренней соршироеки наилучший? Существует ли такой верхний предел скорости сортировки, которого бы не мог достичь нн один программист, квк бы искусен он ни был? Разумеется, не сув4встлеуетп наилучшего возможного способа сортировки; мы должны точно определить, что понимать под словом "наилучший", но не существует наилучшего возможного способа определения слова "наилучший". Аналогичную проблему, связанную с оптимальностью алгоритмов, мы обсуждали в разделах 4.3.3, 4.6.3 и 4.б.4, в которых рассматривались умножение с повышенной точностью н вычисление полиномов. В каждом случае, для того чтобы задача была поставлена в терминах конкретных математических структур, необходимо было сформулировать довольно простое определение "наилучшего нз возможных" алгоритма. И в каждом случае перед нами вставали интереснейшие проблемы, настолько сложные, что они до сих пор полностью не решены.
Так же обстоит дело и с сортировкой: были получены некоторые интересные результаты, но осталось еще много интригующих вопросов, на которые до снх пор нет ответов. Изучение внутреннего механизма методов сортировки обычно бьшо направлено на минимизацию числа сравнений ключей прн сортировке п элементов или слиянии т элементов с я элементами, или выборе Г-го наибольшего элемента из неупорядоченного набора п элементов. В разделах 5.3.1-5.3.3 эти вопросы обсуждаются для общего случая; в разделе 5.3.4 рассматриваются аналогичные вопросы с интересным ограничением: схема (структура) сравнений должна быть, по сути, заранее фиксированной.
Другие интересные теоретические вопросы, связанные с оптимальной сортировкой, можно найти в упражнениях к разделу 5.3.4 и в разделах 5.4.4, 5.4,8 и 5.4.9, в которых анализируется внешняя сортировка. Как только появится аналитическая машине. Онв, беэусловно, определит дальнейший путь развития науки. Всякий рээ, когда с ее помощью будет найден какой-либо результат, возникнет вопоос: "Существует ли метод вычислений, которым можно получить на этой машине тот же результат, но эатоатив минимум времени?".
— ЧАРЛЬЗ БЭББИДЖ О864) $.3.1. Сортировка с минимальным числом сравнений Очевидно, минимальное число сравнений ключей, необходимое для сортировки и элементов, равно нулю, поскольку, как мы видели, существуют методы поразрядной сортировки, в которых сравнения вообще не выполнявэтся. В самом деле, можно разработать ИХХ-программы, способные сортировать и, тем не менее, не содержащие ни одной команды условного перехода! (См, упр. 5 — 8 в начале этой главы.) 54ы также встречались с несколькими методами сортировки, которые. по сути, были основаны на сравнении ключей, но время выполнения которых на деле определялось другими факторами, такими как перезапись данных, вспомогательные операции и т.
д. Поэтому ясно, что подсчет числа сравнений — не единственный способ измерения эффективности метода сортировки. Однако в любом случае небезынтерес- но провести тщательное исследование числа сравнений, поскольку теоретический анализ злого вопроса позволит нам более глубоко проникнуть во внутреннюкз природу процессов сортировки, а также поможет отточить мастерство для решения задач, более близких к практике, которые могут возникнуть перед нами в будущем. Исключим из рассмотрения метод поразрядной сортировки, в котором совсем не выполняется сравнений, и ограничимся обсуждением методов, основанных только на абстрактном линейном отношении порядка "<" между ключами, рассмотренном в начале этой главы.
Для простоты мы также ограничимся случаем раэличнмя ключей, а это значит, что при любом сравнении ключей К, и Кз возможны лишь два исхода; либо К; < Ку, либо К, > Ку. (Распространение результатов такого анализа на общий случай, когда допускаются равные ключи, приводится в упр. 3-12.) Ограничения на время выполнения в худшем случае рассматрззваюгсл в работах Ргейззап„Ж!!!ахд, Х Сошрнгег н 5уэа 5сй 47 (1993)., 424-436, Веп-Ашгаш, Са))(,,7. Ссипр.
5уэь 5с!. 54 (1997), 345-370 и Т!зогпр, 5ОПА 9 (199$), 550 — 555. Возьнзжны и другие эквивалентные варианты постановки задачи сортировки посредством сравнений. Если есть и грузов и весы с двумя чашами, то каково минимальное число взвешиваний, необходимое для того, чтобы расположить грузы по порядку в соответствии с весом, если в каждой чаше весов помещается только один груз'! Или же, если в некотором турнире участвуют и игроков, то каково наименылее число парных встреч, достаточное для того, чтобы распреде шть места между соревнующимися в предположенни, что силы игроков можно линейно упорядочить (ничейные результаты не допускаются). Методы сортировки п элементов, удовлетворяющие указанным ограничениям, можно представить с помощькз структуры расширенного бинарного дерева, такого, которое показано на рис.
34. Каждый енугпренний узел (згзображенный в виде кружочка) содержит два индекса 5: у" и означает сравнение клкзчей К; и К .. Левое поддерево этого узла соответствует последующим сравнениям, которые необходимо выполнить, если К; < К „а правое подлерево — тем действиям, которые необходимо предпринять, если К, > Кз. Каждый внешний узел дерева (изображенный в виде прямоугольника) содержит перестановку аз аэ... а„множества (1, 2,...,п), а это обозначает, что было установлено упорядочение К„<К,„« К„.
(Если взглянуть на путь от корня к этому внешнему узлу, то каждое из и — 1 соотношений К,, < Ь;,~,, где 1 < ! < и, — результат некоторого сравнения оз:а,эз или аз+з.аз на этом пути.) Так, на рис. 34 представлен метод сортировки, суть которого состоит в том, чтобы сначала сравнить К~ с К; если К, > К, то продолжать (двигаясь по правому поддереву) сравнивать К. с Кэ. а затем, если К < Кэ, сравнить К1 с Кэ, наконец, если Кз > Кэ, становится ясно, что Кэ < Кэ < Кз. Реальный алгоритм сортировки будет также перезаписывать ключи в массиве, но нас интересуют только сравнения, поэтому мы игнорируем все перезаписи данных. При сравнении К; с К, в этом дереве всегда имеются в виду исходные ключи К, и Кл а не те ключи, которые могли занять 1- и у-ю позиции в массиве в результате перемещения записей.
Возможны и избыточные сравнения; например, на рис. 35 нет необходимости сравнивать 3:1, поскольку из неравенств К| < Кэ и Кэ < Кэ следует Кз < Кэ. Ни- Уровень 0 Уровень 1 Уровень з Рнс. 34. Дерево сравнений для сортировки трех элементов. Рнс. 3$. Пример избыточного сравненнв. какая перестановка не может соответствовать левому поддереву узла 3: 1 на рнс. 35, так что эта часть алгоритма никогда не будет выполняться! Поскольку нас интересует минимальное число сравнений, можно считать, что избыточные сравнения не выполняются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
