Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 50
Текст из файла (страница 50)
С этого момента мы будем иметь дело со структурой расширенного бинарного дерева, в котором каждому внешнему узлу соответствует некоторая перестановка, Все перестановки исходных ключей возможны, и каждая перестановка определяет единственный путь от корня к внешнему узлу; отсюда вытекает, что в дереве сравнений для сортировки и элементов без избыточных сравнений имеется ровно и! внешних узлов. Оптимизации в наихудшем случае. Первая естественным образом возникающая задача — найти деревья сравнений, минимизирующие максимальное число выполняемых сравнений. (Позже мы рассмотрим среднее число сравнений.) Пусть Б(п) — минимальное число сравнений, достаточное для сортировки и эле ментов.
Если все внутренние узлы в дереве сравнений располагаются на уровнях < Й, то очевидно, что в дереве не может быть более 2" внешних узлов. Следовательно, полагая к = Я(п), имеем я( < 2з1ь). Посколысу 5(н) — целое число, можно записать эту формулу иначе, получив нижнюю оценку; 5(п) ) (1Кп!). Заметим, что по формуле Стирлинга (1йп!) = н1кп — и/1п2+ -'1кп+ О(1), В(п) ~~, (1 ь) п(18п) 20эв)+1 (3) (см. упр.
1,2.4-42), а максимальное число сравнений для двухпутевого слияяия определено в упр. 5.2.4-14. Оказывается (см. раздел 5.3.3), что для метода выбора из дерева верхняя оценка числа сравнений либо такая же, как дэя метода бинарных вставок, либо такая же, как для двухпутевого слияния, в зависимости от вида дерева. Во всех трех случаях имеем асимптотическое значение п18н; объединяя верхнюю и нижнюю оценки для о(п), получим 1пп — = 1. л'(п) п18п (4) Таким образом, мы получнлн приближенную формулу для В(п), однако желательно иметь более точную оценку, В следующей таблице приведены значения верхней и нижней границ при малых и. и = 1 2 3 4 5 6 7 8 Я 10 П 12 13 14 15 16 17 (18п() =0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 В(п) = 0 1 3 5 8 11 14 17 21 25 29 33 37 41 45 49 54 Цп) = О 1 3 5 9 11 14 17 25 27 30 ЗЗ 38 41 45 49 65 Здесь В(п) и Е(п) относятся соответственно к методам бинарных вставок и слияния списков.
Можно показать, что В(п) < Е(п) при любом и (см. упр. 2). Как видно из приведенной выше таблицы, В(4) = 5, но Я(5) может равняться либо 7, либо 8. В результате снова приходим к задаче, поставленной в начале раздела 5.2. Каков наилучший способ сортировки пяти элементов? Возможна лн сортировка пяти элементов при помощи всего семи сравнений? Такая сортировка возможна, но сам способ найти не так просто.
Начинаем так же, как прн сортировке четырех элементов посредством слияний, сравнивая сначала К~ . Кэ, затем — Кэ . К4, а затем — наибольшие элементы обеих пар. Эти сравнения порождают конфигурацию, которую можно изобразить диаграммой следовательно, необходимо выполнить около и 18 и сравнений. Соотношение (1) часто называют глеореглвко-информационной нижней оценков, поскольку специалкст э области теории информации сказал бы, что в процессе сортировки проверяется 18 и! "бит информации"; каждое сравнение дает не более одного бита информации.
Такие деревья, как на рис, 34, называют также "вопросниками" (цпеэс1оппюгеэ); их математические свойства исследованы в книге С1аиде Р)сагд, ТЬеог1е дм Яи~ясюппюгев (Раг1э. ДапЩег-''т'11)эгэ 1965) Из всех рассмотренных нами методов сортировки три метода требуют меньше всего сравнений: бинарные вставки (см. раздел 5.2.1), выбор иэ дерева (см. раздел 5.2.3) и простое двухпутевое слияние, описанное в алгоритме 5.2.41). Нетрудно видеть, что максимальное число сравнений для метода бинарньпс вставок равно показывающей„что й < Ь < |1 и с < Ы.
(Для представлении известных отношений порядка между элементами удобно воспользоваться ориентированными графами, такими, что х считается меньше у тогда и только тогда, когда на графе есть путь от х к р,) Теперь вставляем пятый элемент Кь = е в соответствующее место среди (а,6, с1); для этого требуются всего два сравнения, поскольку можно сравнить его сначала с Ь, а затем — с а или ы. Таким образом, остается один из четырех возможных вариантов е а с й с й с а с и в каждом случае достаточно еще двух сравнений, чтобы вставить с в цепочку остальных элементов, меньших ы. Такой способ сортировки пяти элементов впервые обнаружил П В. Демут (Н. В.
Пешпз)з) [Р)з. П. Ь)зез1э, ВзапЕоЫ 11ппегэйу (1956), 41-43). Сортировка посредством вставок и слияния. Изящное обобп|ение изложенного выше метода принадлежит Лестеру Форду (мл.) (1 еэгег Рог|1, Зг.) и Селмеру М. Джонсону (Ышег М. )о(|паол). Поскольку оио объединяет некоторые особенности двух способов сортировки (посредством слияний и посредством вставок), мы назовем этот метод сортирййков посредсзпвом вставок и слплипл.
Рассмотрим, например, сортировку 21 элемента. Начать можно со сравнений десяти пар ключей К|: Кю Кз -'Кь, Кш: Кэ|, затем следует рассортировать посредством вставок и слияния ббльшие элементы пар. В результате получим конфигурацию а| аз аз аь йь аь а| аь аз а|о Ь Ьз Ьь Ь Ьь Ьь Ь Ь Ь Ь|о Ь аналогичную (5). Следующий шаг — вставить элемент Ьз в последовательность (Ьз|п|1оз), а затем — Ьз в последовательность остальных зле~антея, ~си~шик оз.
В результате приходим к конфигурации сь сз сз сь сь сь аь аь аь а| аь ао а|о (8) Ьь Ьь Ьь Ьз Ьь Ьо Ьзо Ьп Назовел| верхние элементы главной цепочкой. Элемент Ьь можно вставить в главную цепочку за три сравнения (сравнив его сначала с с|, затем с сз или сь и т. д.). После этого еще за три сравнения можно переместить в главную цепочку 64 и получить |З| |зз |зз йь йыьь ььз |зы|ыь|о аь й| аз аь й|о (9) Ьь Ьз Ьь Ьо Ь!о Ьз| "Следующий шаг решающий: ясно ли вам, что делать дальше?" При помощи всего четырех сравнений вставляем Ьп (но не Ьз) в главную цепочку. Далее элементы Ьзо, Ьз| Ьь, 6|| Ьй (именно в таком порядке) можно вставить в нужное место в главной цепочке не более чем за четыре сравнения каждый. Аккуратный подсчет числа требуемых сравнений показывает, что 21 элемент можно рассортировать не более чем за 10+6(10)+2+2+3+3+4+4+4+4+4+4 = 66 шагов. Поскольку 265 < 21) < 266, ясно также, что и в любом другом случае необходимо не менее 66 сравнений; следовательно, о(21) = 66 (10) (Прн сортировке с помощью бинарных вставок понадобилось бы 74 сравнения.) В общем случае сортировка посредством вставок и слияния для и элементов выглядит следующим образом.
Ц Сравнить (и/21 непересекающихся пар элементов. (Есля п нечетно, то один элемент не участвует в сравнениях.) й) Рассортировать (ге/21 ббльших элементов пар, найденных на шаге (1), посред- ством вставок и слияния. !6) Для элементов введем обозначении ам аз,..., а(„/зр Ь|, Ьзе..., Ь~„,зр как в (7), где ае < аз « а(„, з~ и Ь, < а; при 1 < 1 < (и/2); назовем Ье н все элементы а главной цепочкой. Не трогая элементов Ь; еери 7' > (и/2), вставим посредством бинарных вставок в главную цепочку остальные элементы Ь в следующем порядке: Ьз Ьз' Ьэ Ь4; Ьы Ь1о " Ьэ' ' Ье„Ье -ы ° °,Ьм,+е; ° ° ° (11) наша цель — сформировать последовательность (1ы 1э, 1з, с4,... ) = (1,3, б, 11, ...
), присутствующую в (11), таким образом, чтобы каждый нз элементов Ье„, Ье,, ы ..., Ье,,+е можно было вставить в гчавную цепочку не более чем за Ь сравнений. Обобщая (7)-(9), получим диаграмму эиь, аеь е+е еееь е+е ь ь еь„,эе е„ „те ьеь на которой главная цепочка до ае„1 включительно содержит 21э е + (гь — сь е — 1) элементов, Это число должно быть лееньше 2"; для нас лучше всего положить его равным 2~ — 1, и тогда 1ь г+ Еь — — 2~.
(12) Поскольку $е = 1е для удобства можно положить 1э = 1. В итоге, суммируя члены геометрической прогрессии, найдем 4 =2' — гь е — — 2" — 2' '+1ь з=" =2' — 2' '+" +(-1)"2е = (2"+ + ( — 1)ь)/3. (13) (Любопытно, что точно такая же последовательность возникла при изучении алгоритма вычисления наибольшего общего делителя двух целых чисел; см. упр.
4.5.2- 36.) Пусть Г(п) — число сравнений, необходимьех для сортировки п элементов посредством вставок и слияния. Ясно, что Р(п) = (и/2) + Р((и/2) ) + О((п/21), где функция С описывает обьем работы, выполняемой иа шаге (ш). Если га г < т < гы то, суммируя по частям, получаем О(ш) = 1г 7(!1 — гу г) + Й(пг — !а г) = йгп — (Го + гг + . - + га г), (15) у=г Положим юа = со+!г+" +!», = (2'+'73), (16) и тогда (гно,гнг гнз,гнз,гне,...) = (О, 1, 2, 5, 10, 21,...). В упр.
13 показано, что Г(п) — Г(п — 1) = й тогда и "только тогда, когда гна < п < юеег, (17) а последнее условие эквивалентно неравенствам 2а+' 2"+з — <и<— 3 — 3 или й+ 1 < 183п < й+ 2; следовательно, ~84 1' (18) (Эта формула получена А. Хадьяном (А. Наг(!ап) (Р!г, О. !)ген!з, ()п(т.
о( М!ппензса (1969), 38-42].) Отсюда вытекает, что функция Г(п) выражается на удивление простой формулой Г(~) = ~~ '~!8-,'й1, (19) амг которан очень похожа на формулу (3) для метода бинарных вставок. В замкнутом виде зту сумму можно найти в упр. 14. Воспользовавшись (19), нетрудно построить таблипу значений функци~ Г(п); имеем я=12345 б 7 8 91011121314!51617 (!8п(1 =О 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 Г(п) = О 1 3 5 7 10 13 16 19 22 26 ЗО 34 38 42 46 50 н 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ((йп!) = 53 57 62 66 70 75 80 84 89 94 98 103 108 113 118 123 Г(п) = 54 58 62 66 71 76 81 86 91 96 101 106 111 116 121 126 Обратите внимание на то, что Г(п) = ~!8п!'! при 1 < и < 11 и при 20 < и < 21! таким образолц прн этих значениях и сортировка посредстном вставок и слияния оптимальна: 5(п) = ()йп!"! = Г(п) при и = 1, ..., 11, 20 и 21. Задачу нахождения функции Я(п) поставил Гуго Штейнгауз (Нцйо Яье!и!гаиз) во втором издании своей классической книги Л4аг)гегпаг!са! Яларзйогн (ОхХогг! Вп1- тегн!гу Ргеэз, 1950, 38-39)е.
Он описал метод бинарных вставок, который является наилучшим способом сортировки и элементов при условии, что п-й элемент не рассматривается до тех пор, пока не рассортированы первые п — 1 элементов; он ь Есть русский перевод первого издания этой кннгн: Штевнгауз Г, Матенатнческнв калевдо. скоп. — М.: Гостекнздат, !Эеэ. — Прим.персе, Таблица 1 знлчения ФАИТОРНАлОВ В дВОичнОН системе счисления же сделал предположение о том, что метод бинарных вставок оптимален н в общем случае. Несколько лет спустя Штейнгауз сообщил (Са!сииа Ма»Ь. Яос. СоЫел 3пЫее Сопппетогабгш 2 (1959), 323-327), что двое его коллег, С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
