AOP_Tom3 (1021738), страница 50
Текст из файла (страница 50)
Предполагается, что Н > 2. 01 БТАНТ ЕМТб 0 1 02 ЕМТ1 1-М 1 ОЯ ЕИТ2 И 1 04 ЕМТБ Н-1 1 Об ЛНР 1Р 1 К1. Начальная сгаиояка. Очистить стек 1 « — 1. г «- А«. Ь « — 1 Перейти к шагу К2 (опустнть проверку 1=г). КО, Поместить я стек [г14 =1 — 1] (г, Ь) ~ стек. г11 «- 1 —,1'. «' «- 1. нг.н ~ [г13 = « — 1] [г13 = «-1] «« — 1, 1 « — г. КЗ. П рве ить наличие 1 и К . Млндп«нй разряд гА +- разряд Ь ключа Кь Перейти к шагу К4, если он равен О. ~,У~~ми;, «,-1. Мь-,— « Перейти к шагу К8, если 1 < 1 [Н4=1 — «] Кб П опе игь наличие О и К [г13 = « — 1] [ПЗ = « — 1] К4 Увеличить «.
««- «+ 1. Перейти к шагу КЗ, если «< 1. г13 « — «. Об 9Н 07 Об 00 10 11 1Н 12 1Я ЗН Ц 1б 1б 17 бН 10 10 БН 20 21 22 22 7Н 24 25 гб 27 4Н гв 20 1ИСб 1 БТ2 БТАСК,О(А) БТБ БТАСК,б(В) ЕММ1 0,4 ЕМТ2 -1,3 ЕМТЗ 0,1 ЕИТ4 0,2 1МСЗ 0,4 ЕОА 1МРОТ,З БНВ О,б ЗАЕ 4Р ОЕС4 1,3 14И 8Г 1МС4 0,3 ЕОА 1ИРОТ+1,4 БНВ О,б ЛАО бВ 10А 1МРОТ+1,4 10Х 1МРОТ,З БТХ 1МРОТ+1,4 БТА 1МРОТ,З РЕСЗ -1,4 13МР ЗВ 1МСЗ 0,4 Я Я Я Я Я А А С' СФ С' С' С" + Х Сл + Х С" С" С" Сл В В В В С' — Х С' — Х А — Х Младший разряд гА +- разряд 6 ключа Кз+«.
Перейти к шагу Кб, если он равен 1. К7. Поменять местами К К. ЯО ВН Я1 562 ОР 0ЕСБ 1 А А — С А — число итераций, в которых ! < и;  — число операций обмена записей; С = С' + С" — число проверок разрядов; С вЂ” число случаев, когда Ь > ги на шаге К8: К вЂ” число случаев, когда Ь < т, 1 = 1 на пзаге К8;  — число случаев, когда Ь < т, 1 < ! на шаге К8;  — число случаев, когда Ь < гп, 1' = и на шаге К8:  — число случаев, когда что-либо помещается в стек; Х вЂ” число случаев, когда 1 < у на шаге Кб.
(29) По закону Кирхгофа В = А — С вЂ” К вЂ”  — Л, так что общее время выполнения равно 27А + 8В + 8С вЂ” 23С вЂ” 14К вЂ” 178 — 19Л вЂ” Х + 13 машинных циклов. За счет усложнения программы можно несколько ускорить циклы проверки разрядов (см. упр. 34). Обменную поразрядную сортировку можно также ускорить, если при достаточно малых значениях разности и — ! применять простые вставки, как это сделано в алгоритме 14, но мы не будем задерживаться иа таких усовершенствованиях. Проанализируем время выполнения обменной поразрядной сортировки в двух случаях, которым соответствуют разные наборы условий. у) Пусть )1с = 2 и ключи, которые следует рассортировать, — просто числа О, 1, 2,..., 2™ — 1, расположенные в случайном порядке.
й) Пусть т = оа (неограниченная точность) и ключи, которые необходимо рассортироватгч -- независимые, равномерно распределенные в промежутке [0..1) действительные числа. Анализ случая (!) относительно прост, поэтому он оставлен читателю в качестве упражнения (см. упр. 35). Случай (й) более сложен, но ега мы также оставили для упражнений.
В следующей таблице приведены грубые оценки результатов анализа в там и другом случаях. ЯЯ ЕИТ4 -1,3 А — С ЯЯ 0ЕС4 0,2 А — С Я4 142 18 А — С Я5 0ЕС4 0,1 А — С вЂ” Л Яб АМ 1В А — С вЂ” 11 Я7 54МЕ 98 А — С-б — К ЯИ 1МС1 1 К ЯЯ 2Н ЯАИ2 18 К+Я 40 ОН ЕИТ1 1,2 5+1 41 Ь02 ВТАСК,6(А) 5+ 1 42 РЕС1 0,2 5 + 1 4Я Е06 БТАСК,6(В) Я + 1 44 0ЕС6 1 5+ 1 45 ЯВИМ 28 5+1 Время работы программы обменной юших показателей: К8.
П ове ить ооубме сл чаи,[г14 неизвестна) Перейти к шагу К10, если Ь = гп, иначе — 6 с — Ь вЂ” 1. г14 с- 1'. г14 с- у — и. Перейти к шагу К2, если 1' = г, г14 с- у' — 1. Перейти к шагу К2, если у <1. Перейти к шагу К9, если у ф1. ! с-1+1, Переход, если ! ф г. К10. Извлечение из стека. Стек ~ (г,6). Перейти к шагу К2, если стек ие пуст. 1 поразрядной сортировки зависит от следу- А В С С К О 1 э тР7 е —,'Х (30) Величина Случай (1) У 1,'Х16Х К16Х 1~Ч 2 о Случай (й) аК вЂ”,'Ф16 У Х1к Д1 0 —.Х 1 г(а 1)~~ г(а —,'К 4( + Здесь а = 1/!и 2 — 1.4427. Заметим, что среднее число обменов, проверок разрядов и обращений к стеку, по существу, одинаково в обоих случаях, несмотря даже на то, что в случае (й) число итераций на 44% болыпе. На сортировку Х элементов в случае (й) наша 61Х-программа затратит в среднем приблизительно 14.41т'1п_#_ машинных циклов.
Это число можно сократить примерно до 11.5 К1пХ, если воспользоваться предложением из упр. 34. Соответствующая величина для программы Я равна 11.7Ж1п У, но и ее можно уменьшить до 10.6 У 1и а', если воспользоваться предложением Синглтона и выбрать медиану из трех ключей. В случае равномерного распределения данных обменная поразрядная сортировка отнимает в среднем примерно столько же времени, сколько и быстрая сортировка; на некоторых компьютерах она выполняется немного быстрее, чем быстрая сортировка. В упр. 53 показано, в какой мере замедляется этот процесс при неравномерном распределении. Важно отметить, что весь наш анализ основан на предположении о том, что все ключи различны.
Обменная поразрядная сортировка в таком вндс, как описано выше, не очень эффективна, если имеются одинаковые ключи, поскольку она проходит через несколько итераций, каждая из которых требует определенного времени для разделения множества одинаковых ключей до тех пор, пока 5 не станет > т. Один приемлемый способ исправления этого недостатка предложен в ответе к упр.
40. Как обменная поразрядная сортировка, так и быстрая сортировка основаны на идее разбиения. Записи меняются местами до тех пор, пока массив ие будет разбит на две части: левый подмассив, в котором все ключи < К при определенном К, и правый подмасснв, в котором все ключи > К. При бьютрой сортировке в качестве К выбирается реальный ключ из массива, в то время как при обменной поразрядной сортировке, по существу, выбирается некоторый искусственный ключ на основе двоичных представлений. Что касается исторической стороны дела, то обменную поразрядную сортировку открыли П.
Хильдебрацдт, Г. Исбитц, Х. Райзинг и Ж. Шварц [см. Р. Н11оеЬгапог, Н. 1эЫг, Н. Н1э1пя, 3. ЯсЬзчаг1в, .7АСМ 6 (1959), 156 — 163] примерно за год до изобретения быстрой сортировки. Существуют н другие схемы разделения; например, Джон Мак-Карти (доЬп МсСагьЬу) предложил выбирать К - -(и+ с), если известно, что все клк1чи находятся в диапазоне между и и ь.
Еще одну стратегию разделения предложил М. Х, ван Эмден (М. Н. кап Ешбеп) [САСМ 13 (1970), 563 — 567]: вместо того чтобы выбирать К заранее, мы "узнаем", каким может быть хорошее значение К, отслеживая в процессе разделения изменение величин К' = шах(Кп..., К;) и К" = ппп(К,..., Кг). Можно увеличивать ю' до тех пор, пока не встретится ключ, больший К', а затем начать уменыпать у, пока не встретится ключ, меньший К", после чего поменять их местамн н?'или уточнить значения К' и К".
Эмпирические тесты этой "интервальной сортировки с обменом" показывают, что она осуществляется несколько медленнее, чем быстрая, а теоретический анализ выполнить очень сложно. Б значительной мере затруднение во время анализа вызывает тот факт, что записи в падмассивах после разделения уже нельзя считать размещенными в случайном порядке. Это единственный метод, обсуждаемый в данной книге, для поведения которого еще не найдено адекватного теоретического объяснения.
Обобщение обменной поразрядной сортировки для системы счисления с основанием, большим 2, обсуждается в разделе 5.2.5. вАснмптотические методы. Анализ алгоритмов обменной сортировки приводит к некоторым особенно поучительным математическим задачам, которые позволяют больше узнать о способах определения асимптотического поведения функции. Например, при анализе метода пузырька [формула (9)) мы столкнулись с функцией И;, = —, ~~~ э!г" '.
1 (31) 0<г<э<п Какой вид имеет асимптотическое выражение для этой функции? Можно действовать так же, как при исследовании чи<ла инволюпий [формула 5.1.4-(41)). Поэтому, прежде чем двигаться дальше, полезно еще раз просмотреть материал, изложенный в конце раздела 5.1.4. Исследование формулы (31) показывает, что вклад при а = и больше, чем вклад при а = и — 1 и т. д. Это наводит на мысль о замене а на и — з. Мы скоро увидим, что на самом деле удобнее всего применить подстановки 1 = п — а+ 1, ти = и+ 1, в результате которых формула (31) примет вид — И~„, ~ = — ~~~ (га — 1)! ~~~ г (32) гп гп! ' тйс<т 0<всю — ! Для внутреняей суммы существует хорошо известный асимптотический ряд, полученный из формулы суммирования Эйлера: г = — — — (У вЂ” бп) + — (1 — 1)(Х вЂ” бш) + ' ' ' 1 в 1 — 2 1 2 2! а«.л' = - ~ (,) 8,(л'- -4„)+0Р'-") (33) уеа (см.
упр. 1.2.11.2-4). Следовательно, наша задача сводится к анализу сумм вида — (тп — 1)! (т — 1)'1", й > — 1. (34) т) ' ~<с< Как и в разделе 5.1.4, можно показать, что при значениях 1, больших т'~в+', члены суммы пренебрежимо малы: 0(ехр( — пз)). Значит, можно положить | = 0(т~~~э') и заменить факториалы по формуле Стирлинга; (гп — !)! (ги — !)' гп! и ш ~ 12тпт 12рл Зтз 4шз 5т4 / Таким образом, нас интересует асимптотическое выражение для суммы гь(т) = ~ ~е / 1, й> — 1. 1<г<т (35) (Суммирование здесь также можно было бы распространить на весь диапазон 1 < ! < оо, не изменив при этом значения аснмптотического выражения суммы, поскольку, как указано выше, входящие в сумму значения при ! > гп'/э ' пренебрежимо малы.) Пусть дь(х) = х"е — * и /ь(х) = дь(х/т/2т). По формуле суммирования Эйлера при й > 0 получим г ' р Е /ь(!) = / /ь( ) (*+ Š—.,' (/ьб "( ) - /," ."(О)) + Л„ о<с< 1=1 р+! г'" Вр — — / Вр((х))/„(х) г(х Р' о — — ) о(/ Ь,'"оОгр) =о[ -'о).
~зо 2 Гго ге*~~ — 1г~ер — 1 — / / 1(х)Ах=2/ г!х= / Ну Я~ о о о У ( е " — 1 / 7 е " гп аУ+ / — Ну — !и— о У У 2 = — 7 — !пт+ !п2+ 0(е ™/з). Теперь у нас достаточно формул и фактов для того, чтобы вывести, наконец, ответ, который, как показано в упр. 44, имеет внд И'„= 2гй!пгп+ 2(7+!п2)гп — з~/2ягв + 3 + 0(п ), ш = и+ 1. (37) Этим завершается анализ метода пузырька.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
