Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 81
Текст из файла (страница 81)
В результате применения этого метода записи вспомогательной области обычно переставляются.) Тот же трюк применяется при слиянии сначала зон Я~ и 2в, затем — 2в и 2в, Я ~ и 2; для этого необходимо выполнить О(глп) = О(5() операций. Поскольку ни один элемент ие имел более и инверсий, часть массива 2~ ... Ям оказывается, таким образом, полностью рассортированной. Для окончательной "доводки" рассортируем записи ЕЕяэ~ в,... Е(и методом вставок за О(вв) = О(Ю) шагов. В результате в наибольших элементов окажутся в области А.
Затем применим все тот же трюк с областью А и сольем ЕЕ~... Йя-ы с ЕЕяэ~-в,. Ви(но поменяем везде ролями "левое" и "правое', а также отношения меньше" и "больше" ). В конце рассортируем записи ЕЕив.ь .. ЕЕя методом вставок. Последующее усовершенствование рассматривается в работе Ю. Каса)ыпеп, Т. Раээлел, 1. Тенко!а, №гг(1с Х Сотриг1л» 3 (1996), 27-40. Проблема успюячнеостлв слияикя на месте рассматривается в ответе к упр. 5,5-3. 19.
Вагоны можно перенумеровать таким образом, чтобы в конечной перестановке их номера были упорядочены: 1 2 ... 2"; так что это, по существу, задача сортировки. Прогоним сначала первые 2" ' вагонов через и — 1 тупиков, расположив нх в порядке убывания номеров и поместив их в и-й тупик тэк, чтобы наименьший элемент оказался на входе в тупик (на вершине стека). Затем прогоним остальные 2" ' вагонов через и — 1 тупиков, расположив их в порядке возрастания непосредственно перед и-м тупиком, И наконец, сольем эти две последовательности очевидным способом. 20. Дополнительную информацию можно найти в работе В.
Е. Таг1ап, ЕАС57 19 (1972), 341-346. 22. См. Елуоппайол Ргосеаяля Е егвегв 2 (1973), 127-128. 23. Слияние можно представить в виде бинарного дерева, все внешние узлы которого находятся на уровнях !16Ж) н !16л1~!. Таким образом, максимальное число сравнений равно длине минимального внешнего пути на бинарном дереве с 5Е внешними узлами (формула 5.3.1-(34)) минус Е!Š— 1, поскольку при Е(т, и) = гл + л — 1 получим максюгум и имеется Е!Š— 1 слияний (см, также соотношение 5.4.9-(1)). Обобщенная методика анализа асимптотических свойств тако~о рекуррентиого соотношения при помощи преобразования !неллина представлена в работе Р.
Г!а)о!ег, М. Со!ш, Асэа ЕпГогша41са 31 (1994), 673-696, В частности, в ней показано, что среднее количество сравнений равно Х!6гŠ— 65!+ 5(16)т")Еэ'+ О(1), а дисперсия .345М. Здесь б есть непрерывная функция с периодом 1 и средним значением О, а 1 1 1 ч 2 2т+ 1 б — — -+ — ~ 1а— 1и 2 2 1п 2 ~', (лг + 1)(пт + 2) 2т = 1.24815 20420 99653 84390 29565 64329 53240 16127+. Суммарное число сравнений при Х -э оо хорошо аппроксимируегся методом нормального распределения; дополнительный анализ выполнен в работе Н.-К.
Нкааб, М. Сгашег, йаЫош Ягысгвгаэ н А!3огййшз 8 (1996), 319-336; 11 (1997), 31-96- РАЗДЕЛ 5.2.5 1. Нет, потому что после первого просмотра поразрядная сортировка вообще не будет выполняться, если распределяющая сортировка неустойчива, (Но предложенный способ распределяющей сортировки вволсно было бм применить к поразрядной СЦ-сортировке, на что указано в последнем абзаце этого раздела.) 2. Это алгоритм "антиустойчивой" сортировки, прямо противоположной устойчивой.
Элементы с одинаковыми ключами располагаются в обратном порядке, поскольку при первом просмотре записи сканируются от Кл до Кь (Это действительно удобно, так как в строках 28 н 20 программы К Л приравнивается к О, но, разумеется, вовсе необкзательно выполнять первый просмотр в обратном направлении.) 3. Если стопка 0 не пуста, то ВОТИ(0) уже указывает на первую запись; если же она пуста, то мы устанавливаем Р ~- РОС(ВОТИ(0) ), а штоследствии устанавливаем в 11ИК(Р) указатель на первую непустую стопку.
4. Если осталось выполнить четное число просмотров, то поместить стопку 0 в начало стека (в очередности от первых элементов к последним), затем стопку 1, ., стопку (М вЂ” 1); в результате записи будут упорядочены относительно уже проанализированных разрядов ключей. Если осталось выполнить нечетное число просмотров, то поместите в начало стека стопку (М вЂ” 1), затем — стопку (М вЂ” 2), ..., стопку О, в результате записи расположатся в обратном порядке относительно уже рассмотренных разрядов ключей. (Это правило, по-видимому, впервые опубликовал Э.
Х. Франц (Е. Н. Гг(епй) (Х4СМ 3 (1956), 156, 165-166).) 5. Замените строку 04 строкой ЕИТЗ 7, а таблицы 8330 н 3580 следующими таблицалпа 338Ы 1.02 КЕТ, 1(1: 1) 502 КЕТ, 1(2: 2) ЬР2 КЕТ,1(3:3) 502 КЕТ.1И:4) 502 КЕТ, 1 (5: 5) 102 1ИРОТ, 1(1: 1) 102 ТИРОТ,1(2:2) 102 1ИР\ГГ, 1(3:3) Е58И Ы1 1ИРОТ,1(51ИК) (Повторить предыдущую строку еще шесть раз.) ПЕС1 1 1 Время выполнения новой программы вычисляется путем замены "3" на "8"; оно равняется (11р — 1) )т'+ 1брМ + 12р — 4Е + 2 прк р = 8.
6. (а). Проанализируйте размещение ()Т + 1)-го элемента. Рекуррентное соотношение 5+1 ЛТ вЂ” 5 рлциепл = — Рми<л+П+ — рмлл ЛТ ' М эквивалентно указанной в условии формуле. (Ь) и-я производная удовлетворяет соотношению дм< ., (х) = (1 — и/М)дмл(х)+ ((1 — х)/М)длгл (х), что доказывается индукцией по л.
Полагая, что х = 1, находим д~хглд(1) = (1 — п/ЛТ)~Ма, поскольку дмо(х) = х Следовательно, шеал(длгл) = (1 — 1/М) М, тат(длгл) = (1 — 2/М)яМ(М вЂ” 1) + (1— 1/М)н М вЂ” (1 — 1/М)э~ М~. (Обратите внимание на то, что производящая функция для Е в программе К есть дмл(х)г.) Т.
Пусть К вЂ” поразрядная сортировка, КХ вЂ” - обменная поразрядная сортировка. Укажем некоторые важные сходные черты и отличия. КХ продвигается от старших цифр к младшим, К вЂ” наоборот. В обоих методах просматриваются цифры ключей, а сами ключи не сравниваются. В КХ всегда М = 2 (см., однако, упр.
1). Время выполнения для К почти не меняется, а для КХ оно очень чувствительно к распределению цифр. В обоих случаях время выполнеяня пропорционально 0((т' 1о8 К), где К вЂ” диапазон измененик ключей, но константа пропорциональности для КХ больше. С другой стороны, если цифры старших разрядов ключей распределены равномерно., то среднее время выполнения для КХ будет равно 0(Х!об К) независимо от величины К.
Сортировка Н требует наличии полей связи, а НХ работает с "минимальной памятью". Внутренний цикл в Н больше подходит для компьютеров с конвейерной архитектурой. 8. При последнем просмотре стопки следует сцепить в другом порядке; например, если М = 255, то стопка (10000000)э должна быть первой, за ней — стопка (10000001)г, стопка (11111111)э, стопка (00000000)ы стопка (00000001)м ..., стопка (0111П11)2 Это изменение порядка сцепления легко осуществить путем модификации алгоритма Н или изменения стратегии распределения памяти при последнем просмотре (см. табл. 1). 9. Можно сначала отделить отрицательные ключи от положительных, как в упр. 5.2.2- 33, или же при первом просмотре преобразовать ключи и записать их в дополнительном коде.
Можно также после последнего просмотра отделить положительные ключи от отри- цательных, изменив порядок расположения последних, но метод из упр. 5,2.2 — ЗЗ для этого уже не ггщится. 11. Без первого просмотра ключи при помощи нашего метода все равно будут полностью рассортированы, потому что (па чистой случайности) ключ 503 уже предшествует ключу 509. Без первгкх двух просмотров было бы 1+ 1+ 0+ 0+ 0+ 1+ 1+ 1+ 0+ 0 = 5 инверсяй, 12. После обмена Н» с В(р) на шаге М4 (упр, 5,2-12) можно сравнить К» с К» ь Если К» меньше, то сравниваем его с К„м К» з, ..., пока не встретим К» > Лм Тогда устанавливаем Щ+и...,В» мВ»)»- (В»,Вг+и, В» ~)„не менял полей 1155, Удобно принудительно поместить с левого конца массива искусственный ключ Ко, который < всех других ключей, 14.
Если ясходная перестановка карт требует 5 чтений в смысее упр, 5,1.3 — 20 и если при каждом просмотре карты раскладываются в т стопок, то придется выполнить яе менее (!ойм Ц просмотров. (Рассмотриге обратный переход — от упорядоченной колоды к исходной; прн каждом просмотре число чтений увеличивается не более чем в и» раз.) Данная перестановка требует четырех чтений для возрастающего порядка и десяти чте- ний длв убывающего порядка. Поэтому сортировка в порядке убывания требует четырех просмотров при двух стопках и трех просмотров при трех стопках, И обратно, этого оптимального числа просмотров достаточно для сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
