AOP_Tom3 (1021738), страница 2
Текст из файла (страница 2)
Джонсону (Яе)п!ег М. ЯоЬпзоп). Поскольку оно объединяет некоторые особенности двух способов сортировки (посредством слияний н посредством вставок), мы назовем этот метод сортировкой посредстпаом вставок и слияния. Рассмотрим, например, сортировку 21 элемента. Начать можно со сравнений десяти пар ключей Кз: Кг, Кз . 'К4,, Кш: Кго, затем следует рассортировать посредством вставок и слияния ббльшие элементы пар. В результате получим конфигурацию ат аг аз а4 аь аь ат аз ао а!о (7) Ь! Ьг Ьз 64 Ьь Ьь Ьт Ьз 69 Ь!о Ь1! аналогичную (5) Следующий шаг — вставить элемент 69 в последовательность (Ьт,аз,аз), а затем — 67 в последовательность остальных элементов, меньших аг.
В результате приходим к конфигурации сь сг сз 94 сь сь 04 аь аь ат аь ао а!о 64 Ьь Ьь Ьт Ьз 69 Ь!о 6!! Назовем верхние элементы главной цепочкой. Элемент Ьь можно вставить в главную цепочку за три сравнения (сравнив его сначала с с44 затем с сг или сь и т. д.). После этого еще за три сравнения можно переместить в главную цепочку 64 и получить 441 тзг 479 474 тзь 49 !47 479 479 4710 419 97 аз 119 010 (9) Ьь 67 Ьз 69 610 61! "Следующий шаг решающий; ясно ли вам, что делать дальше?" При помощи всего четырех сравнений вставляем 6м (но не 67) в главную цепочку.
Далее элементы Ь!0, Ьо, Ьз, Ьт, 60 (именно в таком порядке) можно вставить в нужное место в главной цепочке не более чем за четыре сравнения каждый. Аккуратный подсчет числа требуемых сравнений показывает, что 21 элемент можно рассортировать не более чем за 10+о(10)+2+2+3+3+4+4+4+4+4+4 = 66 шагов. Поскольку 2вэ < 21~ < 2ва ясно также, что и в любом другом случае необходимо не менее 66 сравнений; следо- вательно, о(21) = 66 (10) (При сортировке с помощью бинарных вставок понадобилось бы 74 сравнения.) В общем случае сортировка посредством вставок и слияния для и элементов выглядит следующим образом. 1) Сравнить (и/21 непересекающихсл пар элементов. (Если и нечетно, то один элемент не участвует в сравнениях.) й) Рассортировать (и/2) ббльших элементов пар, найденных на шаге (1), посредством вставок н слияния. ш) Для элементов введем обозначения ам аз,..., а:,„/эп Ьм Ьм..., 5~в~э~, как в (7), где а~ < аэ < < а(„7э) и Ь, < а; при 1 <1 < ~п/2); назовем Ьэ и все элементы а главной цепочкой.
Не трогая элементов Ь при 7 ) (и/2), вставим посредством бинарных вставок в главную цепочку остальные элементы Ь в следующем порядке: Ьэ,Ьэ,' ЬмЬ4, 'Ьм,Ьэо,...,Ьв, '.. , 'Ьм,Ьм и ° °,Ьм,< ь~ Наша цель — сформировать последовательность (1ы Ьэ, гэ, ~4,... ) = (1, 3, 5, 11, ... ), присутствующую в (11), таким образом, чтобы каждый из элементов Ьм, Ь,„ ..., Ьм гь~ можно было вставить в главную цепочку не более чем за Ь сравнений.
Обобщал (7) — (9), получим диаграмму хэм ~ шц гы ам ~/э к ам Ь Ь м,еэ м,э.э ьм-! на которой главная цепочка до а„~ включительно содержит 2сь ~ + (сь — сь ~ — 1) элементов. Это число должно быть меньше 2"; для нас лучше всего положить его равным 2ь — 1, и тогда Юь ~+Фа=2". (12) Поскольку сэ — — 1, для удобства можно положить 1э = 1. В итоге, суммируя члены геометрической прогрессии, найдем Сь — 2 — 1ь э — 2 — 2~ ~+сь э= =2" — 2ь ~+ .+( — 1)ь2 = (2"'+ (-Ц")/3. (13) (Любопьпно, что точно такая же последовательность возникла при изучении алгоритма вычисления наибольшего общего делителя двух целых чисел; см.
упр. 4,5.2— 36.) Пусть Е(п) — число сравнений, необходимых для сортировки и элементов посредством вставок и слияния. Ясно., что Е(п) = (и/2) + )г((п/2)) + С((п/2)), (14) где функция 0 описывает объем работы, выполняемой на шаге (ш). Коли га г < т < 1а, то, суммируя па частям, получаем а-~ су(ш) =Яу(11 — 11 1)+а(пг — 1,,) =ат — (19+11+- +1а г). (15) Положим ю, = 1о + 1, + " + Га 1 = '(2""'/3), (Гб) и тогда (гиги гог,игг:зиз,ии,...) = (О, 1, 2, 5, 10, 21,...). В упр. 13 показано, что Р(п) — Р(п — 1) = lс тогда и только тогда, когда гиа < п < ига+1, (17) а последнее условие эквивалентно неравенствам 2аьз 2"+з — <и<в 3 3 или )с+ 1 < 183п < й + 2; следовательно, Е(п) Е(п 1) ~!8 4зп (18) (Эта формула получена А.
Хадьяном (А, Наббап) [РЬ. В. 1)зез19, Вп1у. о1 Мшпезо1а (1969), 38 — 42).) Отсюда вытекает, что функция Е(п) выражается на удивление простой формулой т; (1 й~) (19) а=1 которая очень похожа на формулу (3) для метода бинарных вставок. В замкнутом виде эту сумму можно найти в упр. 14. Воспользова,вшись (19), нетрудно построить таблицу значений функции Г(п); имеем п = 1 2 3 4 5 6 7 8 9 10 11 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 7 10 13 16 19 22 26 ЗО 34 38 42 46 50 п 18 19 20 21 22 23 24 25 26 27 28 29 ЗО 31 32 ЗЗ (18пЦ = 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 Обратите внимание на то, что К(п) = (18пЦ при 1 < п < 11 и при 20 < п < 21; таким образом, при этих значениях и сортировка посредством вставок и слияния оптимальна: Я(п) = (18пЦ = Р(п) прн п = 1, ..., 11, 20 и 21. (20) * Есть русский перевод первого издания втой книги: Штейнгауз Г Математический калейдоскоп.
— М. Гостекиздат, 1949. — Прим, нерее. Задачу нахождения функции 8(п) поставил Гуго Штейнгауз (Нпйо 81ешЬапз) во втором издании своей классической книги МагЛешабга( бпарэ!югэ (ОхЕогс1 Вшуегзйу Ргеэз, 1950, 38 — 39)". Он описал метод бинарных вставок, который является наилучшим способом сортировки п элементов при условии, что п-й элемент не рагсматривается до тех пор, пока не рассортированы первые и — 1 элементов; он Таблица 1 ЗНАЧЕНИЯ ФАКТОРИАЛОВ В ДВОИЧНОЙ СИСТЕМЕ Сг1ИСЛЕНИЯ же сделал предположение о том, что метод бинарных вставок оптимален и в общем случае. Несколько лет спустя Штейнгауэ сообщил (Са(си!!а МасИ.
Яос. Со)<Зеп,7иЫ!ее Сопилетога1!оп 2 (1959), 323 — 327], что двое его коллег, С. Трибула (8. ТгуЬц!а) и Чжен Пинг (Р. Степ), "недавно" опровергли его предположение и нашли значения о(п) при тг < 11. Вероятно, Трибула и Чжен Пинг независимо пришли к сортировке посредством вставок и слияния, о чем вскоре появилась публикация Рогб, 3оЬпэоп, АММ 66 (1959), 387-389. После открытия сортировки посредством вставок и слияния первым неизвестным значением функции о(п) оставалось о(12).
Из табл. 1 видно, что число 12! довольно близко к 2гэ, поэтому существование 29-шаговой процедуры сортировки 12 элементов весьма маловероятно. Для решения этого вопроса Марком Уэлсом (Маг)с %е!1э) был предпринят продолжительный вычислительный эксперимент (продолжавшийся на компьютере Машас П около 60 ч), который показал, что о(12) = 30 (Ргос. !Р!Р Сопйгелэ 65 2 (1965), 497-498). Итак, процедура вставок и слияний оказывается оптимальной и при и = 12.
"Более глубокий анализ. Чтобы более тщательно исследовать функцию 5(п), вниг мательно изучим диаграммы частичного упорлдочения, подобные (5). Полученные после нескольких сравнений сведения можно представить в виде ориентированного графа. Этот граф в силу транзитивности отношения "<" ие содержит циклов. Следовательно, его всегда можно изобразить таким образом, чтобы все дуги были ориентированы слева направо; поэтому удобнее удалить из диаграммы стрелки.
В результате диаграмма (5) преобразуется в (1)г (10)г (ПО)г (ПООО)г (ППООО)г (10П010000)г (100П10ПОООО) г (100П10П0000000)г (10П000100ПООООООО)г (ПОП1010П П 100000000) г (100П000010001010100000000)г (П1001000ПООППП0000000000)г (10П100П00101000ПООП6000000000)г (101000100ПООООП10П0010100000000000)г (100ПОООООП10П10П10П1010ПООООООООООО) (100ПОООООП10П10П10П1010П000000000000000)г (1010000ПОПП ПОП10П10ПООПОП000000000000000)г (1оп010шпашапоопоо101ооп1оопооооооааооооооао) (П0110000001010П100100ПОООООП0100010010000000000000000)г (10000П 10000ПОПОО П10П П 1001000001010П 01000000000000000000) г = 3! = 4! = 5! = 6! = 7'. = 8! = 91 = 10! = и! = 12! = 13! = 14! = 15! = 16! = 17! = 18! = 19! = 20! (21) а с е Пусть С вЂ” такой ориентированный граф; обозначим через Т(С) число перестановок, согласующихся с С, т.
е. число способов разметки вершин графа С целыми числами (1,2,...,и) так, чтобы чнг ю в верпзине к было меньше числа в вершине у, если дуга х -э у принадлежит С. Вот пример перестановки, согласующейся с (21): а = 1, Ь = 4, с = 2, Ы = 5, е = 3. Мы проанализировали функцию Т(С) для разли шых С в разделе 5.1.4, в котором было отмечено, что Т(с) есть число вариантов топологической сортировки графа С. Пусть С граф из и элементов, который можно получить посте й сравнений; определим эффективность графа С функцией п! 2ьт(С) (22) (Эта идея принадлежит Фрэнку Хвангу (Ггапй Нгмапб) и Шень Линю (БЬеп 1.п1).) Строго говоря, эффективность не есть функция лишь самого графа С вЂ” она зависит от того пути, которым мы пришли к С в процессе сортировки, однако для простоты закроем глаза на эту маленькую неточность.
Выполнив еще одно сравнение элементов 1 и у, получим два графа (С1 и Сз): один -- для случая К; < К, а другой для случая К, > К . Ясно, что т(с) = т(с ) + т(с ) Если т(с~ ) > Т(С»т), то имеем т(с) < 2т(с,), Е(С1) = -- ' = — —,— < Е(С). и! е(с) т(с) 2ь+'Т(с,) 2Т(С1) (23) Следовательно, каждое сравнение приводит к графу меньшей или равной эффективности; нельзя увеличить эффективность за счет дополнительных сравнений. Заметим, что если С совсем не содержит дут, то 1с = 0 и Т(С) = п!, т. е.
начальная эффективность равна 1. Есчи же граф С представляет окончательный результат сортировки, то он выглядит, квк отрезок прямой, и Т(С) = 1. Так, например, если нам нужно построить процедуру сортировки пяти элементов за семь яли мепсс сравнений, то необходимо получить линейный граф , эффективность которого равна 5!/(2т х 1) = 1211/128 = 15/16. Отсюда следует. что все графы. возникающие в процессе сортировки, должны иметь эффективность > 1'; если бы появился какой-нибудь граф меньшей эффективности, то, по крайней мере, один из его потомков тоже имел бы меньшую эффективность и мы бы, в конпе концов, пришли к линейному графу с эффективностью < —,"-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
