AOP_Tom3 (1021738), страница 182
Текст из файла (страница 182)
Ргас(!айаг, А18оПг(пп(са 14 (1995), 340-354.) 15. Продублируйте команды реализации шагов Ь3, Ь4 и Ьб для случаев, когда известна, что Ь, равно р или д. (Алгоритм можно еще более усовершенствовать, удалив из внутреш|его цикла присвоение з !- р (илн з !- 9), просто переименовав регистры! Замените, например, строки 20 и 21 строкой ЬУЗ 18Р02,1(Ь) и продолжайте далее, считая, что р находится в г13, з — в г11, а значение переменной Ь„ Ь, заведома равна р. Имея двенадцать копий внутреннего цикла, соответствующих различным перестановкам (р, 9, г) относительно регистров (г11, г12, г!3) и различной информации а 1„, можно сократить среднее время работы до 8М 18 Ж+ О(Ю).) 16.
Полученный алгоритм будет работать чуть быстрее алгоритма Ь (см. упр. 5,2.3-28). 17. Рассматривайте новую запись как подмассив длиной 1. Повторяйте слияние двух наименьших подмассивов, имеющих одинаковую длину. (Полученный алгоритм сортировки, по существу, такой же, как алгоритм Ь, талька слияния падмассивов выполняются в другал! порядке.) 18. Да, на это, по-виднмому, очень сложно В простейшем известном методе используется следующее искусное посгроение (ДАН СССР 186 (1969), 1256 — 1258!.
Пусть и ч'Х. Разделим массив на гл+ 2 "зон" Я!... Я, 3,в!.! У„,.~з, где зона 2 з ! содержит !г' шос1 а записей, а остальные зоны содержат ровно па и записей. Поменяем местами записи зоны Я,э! с зоной, в которой содержится Нм; теперь массив имеет вид Я!... З, А, где каждая из зон Я! .. Я содержит ровно и упорядоченных записей, а А — — вспомогательная область, содержащая з записей, где з — некоторое число из диапазона л < з < 2п, Найдем зону с наименынил! лидирующим элементов! и поменяем ее местами с Я!. Если более одной зоны имеет наименьший лидирующий элемент, выберите ту из них, замыкающий элемент которой будет наименывим. (Для этого потребуется 0(ш+ и) операций.) Затем найдем зону со следующим по порядку лидируюв!им элементом и поменяем ее местами с аз и т.
д. В конце концов. за 0(т(т+ и)) = 0(Х) операций мы перекомпонуем эти т зон таким образом, чтобы ик лидирующие элементы были упорядочены. Кроме того, в соответствии с исходным предположением о характере массива каждый из ключей в зонах х! .. Я ! теперь имеет не более чем а инверсий. Для слияния Я! с Л! можно воспользоваться следующим трюком, поменять местами л! с первыми п элементами А' области А, а затем слить Яг с А', как обычна, но при выводе поменять местами элементы с элементами области л!Яз. Например, если а = 3 и х! < у! < хз < уг < хз < уз, та имеем следующее. Зона 1 Зона 2 х! у! х! у! х! у! х! у! аз хг х! Начальное содержилгое: Обмен с а!: Обмен с х!! Обмен с у!! Обмен с хз: Обмен с уз' Обмен с хз: х! х! хз а! аз аз х! аг аз У! у! Уз Уг Уз У! 92 Уз а! Уз уз а! Уг уз у! аз уз уз гз уз Вспомогательная область а! а! аз х! хз хз а! хз хз а! х! хз а, аз хз а! аз хз а! аз аз (Слияние всегда завершается в тот момент, когда происходит обмен и-го элемента вспомогательной области.
В результате применения этого метода записи вспомогательной области обычно переставляются.) Тот же трюк применяется при слиянии сначала зон 3г и Уг, затем — Уг и Кг, У,„г и 3; для этога необходимо выполнить 0(гпп) = 0(07) операций. Поскольку ни один элемент не имел более и инверсий, часть массива Яг... У оказывается, таким образом, полностью рассортированной. Для окончательной "доводки" рассортируем записи йяэс г йя методом вставок за 0(зг) = О()г') шагов. В резулыате э наиболыпих элементов окажутся в области А.
Затем применим все тот же трюк с областью А и сольем Гсг .. Ея-г с )7яз.г-г. Ея— (но поменяем везде ролями "левое" и "правое", а также отновгения "меньше" и '"больше" ). В конце рассортируем записи Г(я~.г, йя методам вставок. Последующее усовершенствование рассматривается в работе 1. Каса!агпеп, Т. Раэапев, .!. Теи)со!а, №гсйс У. Сошрвс!пб 3 (1996), 27-40. Проблема устойчивости слияния на месте рассматривается в ответе к упр. 5.5 3 19.
Вагоны можно перенумеровать таким образом, чтобы в канечяой перес.гановке их номера были упорядочены: 1 2 ... 2"; так что эта, по существу, задача сортировки. Прогоним сначала первые 2" ' ишанов через и — 1 тупиков, расположив их в порядке убывания номеров и поместив их в и-й тупик так, чтобы наименьший элемент оказался на входе в тупик (на вершине стека). Затем прогоним остальные 2" ' ваганов через и — 1 туликов, расположив их в порядке возрастания непосредственно перед и-и тупиком. И наконец, сольем эти две последовательности очевидным способам 20.
Дополнительную информацию можно найти в работе В.. Е. Тагзап, УАСМ 19 (1972), 341-346. 22. См. ГлГогтасгоп Ргосеэявй 7егсегэ 2 (1973), 127-128. 23. Слияние можно представить в виде бинарного дерева, все внешние узлы каторога находятся на уровнях (!8 Ю! и (!8 Х'!. Таким образам, максимальное числа сравнений равно длине минимального внешнега пути на бинарном дереве с Дг внешними узлами (формула 5.3.1-(34)) минус Х вЂ” 1, поскольку при Г(т, и) = гп+ и — 1 получим максимум и имеется !э' — 1 глиянкй (см. также соотношение 5.4.9 — (1)).
Обобщенная методика анализа асимптотических свойств такого рекуррентнаго соотношения при помощи преобразования Меллина представлена в рабате Р. Р!а)о!еС, М. Оойп, Асга !пГогшаС!са 31 (1994), 673-696. В частности, в ней показано, что среднее количество сравнений равно %18!сг — ВХ + б(!8гэ')!г + О(1), а дисперсия .345%.
Здесь б есть непрерывиаи функция с периодам 1 и средним значением О, а 2 2т+ 1 В = — — — + — У !и !п2 2 !п2 ~-', (т+ 1)(т+ 2) 2т = 1.24815 20420 99653 84890 29565 64329 53240 16127+. Суммарное число сравнений при гг' — э оа харашо аппроксимируется методам нармальнага распределения; дополнительный анализ выполнен в работе Н.-К. Нвавй, М. Сгашег, Вапс)ош Есгисгигеэ и А!Вогййтэ 8 (1996), 319-336; 11 (1997), 81-96 РАЗДЕЛ 5.2.5 1. Нет, потому что после первого просмотра поразрядная сортировка вообще пе будет выполняться, егли распределяющая сортировка неустойчива. (Но предложенный способ распределяющей сортировки можно била бм применить к поразрядной СЦ-сортировке, на что указано в последнем абзаце этого раздела,) 2.
Это алгоритм "антиустайчивой" сортировки, прямо противопатожной устойчивой. Элементы с одинаковыми ключами располагаются в обратном порядке, поскольку при первом просмотре записи сканируются от )(л до )(ь (Это действительно удобно, так как в строках 28 и 20 программы К Л приравнивается к О, но, разумеется, вовсе необязательно выполнять первый просмотр в обратном направлении.) 3.
Если стопка 0 не пуста, то ВОТИ(0) уже указывает на первую запись; если же она пуста, то мы устанавливаем Р +- ЬОС(ВОТИ(0] ), а впоследствии устанавливаем в 1.1ИК(Р) указатель на первую непустую стопку. 4. Если осталось выполнить четное число просмотров, та поместить стопку 0 в начало стека (в очередности от первых элементов к последним), затем стопку 1, ..., стопку (М вЂ” 1); в результате записи будут упорядочены относительно уже праанализированных разрядов ключей.
Если осталось выполнить нечетное число просмотров, то поместите в начало стека стопку (М вЂ” 1), затем — стопку (ЛУ вЂ” 2), ..., стопку 0; в результате записи расположатся в обратном порядке относительно уже рассмотренных разрядов ключей. (Это правило, по-видимому, впервые опубликовал Э.
Х. Френд (Й Н. 571еп<1) (ЗАСМ 3 (1956), 156, 165 166).) 5. Зал~ените строку 04 строкой ЕИТЗ 7, а таблицы КЗБ(( и КЯЯЫ следующими таблицами. КЗБИ 502 КЕУ.1(1:1) Ь02 КЕУ,1(2:2) 1.02 КЕУ,1(3."3) 502 КЕУ,1(4:4) 1.02 КЕУ,1(6:5) 502 1ИРОТ, 1(1: 1) 602 ТИРОТ,1(2:2) 502 1ИРОТ,1(3:3) КЯЯИ 501 ТИРОТ,1(ЬТИК) (Повторить предыдущую строку еще шесть раз.) РЕС1 1 1 Время выполнения новой программы вычисляется путем валуевы "3" на "Я"; оно равняется (11р — 1))У + 16РМ 4 12р — 4Е + 2 при р = Б. 6.
(а). Проанализируйте размещение (%+ 1)-го элемента. Рекуррентное соотношение к+1 М вЂ” к рм(яэць ~~ рмь(ээц + рмяэ М эквивалентно указанной в условии формуле. (Ь) и-я производная удовлетворяет соотношению д("( .,)(в) = (1 — и/М)дмь(э) + ((1 — х)/М)дм+„0(в), что доказываетсЯ индУкпией по и. Полагая, что х = 1, находим дм~"ь.(1) = (1 — и/ЛУ)ьЛУв, поскольку дмо(х) = хм. Следовательно, шеап(дмн) = (1 — 1/ЛУ)ь М, тат(дмя) = (1 — 2/М) М(ЛХ вЂ” 1) + (1— 1/М)ь М вЂ” (1 — 1/М)эЯМэ. (Обратите внимание на то, что производящая функция для Е в программе К есть дмя(х)" ) Т.
Пусть К вЂ” поразрядная сортировка, КХ . — обменная поразрядная сортировка. Укажем некоторые важные сходные черты и отличия. КХ продвшается от старших цифр к младшим, К вЂ” наоборот. В обоих методах просматриваются цифры ключей, а сами ключи не сравниваются. В В.Х всегда М = 2 (см., однако, упр. 1).
Время выполнения для К почти не меняется, а для КХ оно очень чувствительно к распределению цифр. В обоих случаях время выполнения пропорционально 0()У 1оК Л ), где Ы вЂ” диапазон изменения ключей, .но константа пропорциональности для В.Х больше С другой стороны, если цифры старших разрядов ключей распределены равномерна, то среднее время выполнения для КХ будет равно О(Х 1ой)У) независимо от величины К. Сортировка Н требует наличия полей связи, а НХ работает с "минимальной памятью". Внутренний цикл в Н больше подходит для компьютеров с конвейерной архитектурой.
8. При последнем просмотре стопки следует сцепить в другом порядке; например, если М = 256, то стопка (10000000)э должна быть первой, за ней — стопка (10000001)м ..., стопка (11111111)э, стопка (00000000)ю стопка (00000001)г, , стопка (01111111)з Это изменение порядка сцепления легка асувгествить путем модификации алгоритма Н или изменения стратегии распределения памяти при последнем просмотре (см. табл. 1). 9. Можно сначала отделить отрицательные ключи от положительных, как в упр. 5.2,2— 33, или же при первом просмотре преобразовать ключи и записать их в дополнительном коде.
Можно также после последнего просмотра отделить положительные ключи от отрицательных, изменив порядок расположения последних, но метод из упр. 5.2.2-33 для этого уже не годится. 11. Без первого просмотра ключи при помощи нашего метода все равно будут полностью рассортированы, потому что (по чистой случайности) ключ 503 уже предшествует ключу 509. Без первых двух просмотров было бы 1 + 1 + 0 + 0 + 0 + 1 + 1 + 1 + 0 + 0 = 5 инверсий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
