AOP_Tom3 (1021738), страница 172
Текст из файла (страница 172)
12. Очевидный способ — пройти по всему списку, заменяя связи й-го элемента число»» й, и затем перекомпоновать элементы на втором проходе. Описанный ниже более прямой и быстрый способ для случая, когда записи не слишком велики, принадлежит М. Д. МакРТарену (М.
О. Масйагеп). (Для удобства предполагается, что 0 < 11ИК(Р) < ЛР при 1 < Р < ЛР, где Л ш О.) М1. [Инициализация.) Присвоить Р»- НЕКО, й +- 1. М2. [Выполнено?) Если Р = Л (или, что равносильно, если й = Л) + 1), выполнение процедуры заканчивается. МЗ.[Обеспечить Р > й.) Если Р < й,присвоить Р » — ЫИК(Р) и повторить этот шаг.
М4. [Обмен.] Поменять местами Л» и Л(Р). (Предполагается, что ЫИК(й) и ЫИК(Р) также при этом меняются местами.) Затем присвоить 0+- ЫИК(й) 5 ЫИК(й) +- Р, Р+- О, й» вЂ” й+ 1 и вернуться к шагу М2. $ Доказательство состоятельности метода М, Д Мак-Ларена может базироваться иа проверке по индукции следующего свойства, которое всегда выполняется перед началом шага М2: элементы, которые > й в последовательности Р, ЫИК(Р), ЫИК(ЫИК(Р) ), ..., Л, — — это а», ав, ..., ольг ю где В~ ( < Вь в < В, < . < К,„,„,, -- требуемый окончательный порядок записей. Далее, 11МК[1) > ] для 1 < ] ( )с, так что из равенства ЫИК[)) = Л следует ] > Й.
Довольно интересно проанализировать алгоритм М. Д. Мак-Ларена. Одно из его замечательных свойств состоит в том, что алгоритм можно выполнить в обратном порядке и восстановить исходное множество связей из конечных значений 1133[1)... 11МК[Х). Каждая из )Ч! возможных конфигураций на выходе при ) < 11ИК[)) < )Ч соответствует в точности одной из )Ч! возможных конфигураций на входе. Если обозначить через А количество операций Р е- 11МК [Р) на шаге МЗ, то )Ч вЂ” А — число индексов ), таких, что 11ИК []) = ) лоске завершения выполнения процедуры. Это возникает тогда и только тогда, когда ] наибольшее в своем цикле; следовательно, )Ч вЂ” А равно числу циклов перестановки, а А = [ппп О, аге ТЧ вЂ” Ня, тах )Ч вЂ” 1).
См. М. О. МасЕагев, 2АСМ 13 [1966), 404-411; В. Спев, ]. г. Рг[пв, Яс1епсе оГСошрасег РгоКгашт[аб 8 [1987), 139-146. 13. 1)б[ Присвоить г г- )Ч. ]261 Если г = О, остановиться. В противном случае, если СООИТ[К„] ( г, присвоить г е- г — 1 и повторить этот шаг; если СООМТ[К„] = г, уменьшить и СООИТ[К,], и г на 1 и повторить этот шаг. В противном случае присвоить В е- В„] е— СООИТ [К„], СООМТ[К,] е- ] — 1. [)7[ Присвоить Я +- В;, к г — СООМТ[К~], СООМТ[К,] Е- )с — 1, В, < — К, В г- Я, ] Е- к.
Затем, если ) ф г, повторить этот шаг; если ] = г, присвоить В~ г — В, г е- г — 1 и вернуться к шагу [)6'. 9 Для того чтобы убедиться в состоятельности этой процедуры, обратите внимание, что перед началом шш а [)6' все записи Вм которые еще не находятся на своих окончательных местах и для которых 1 > г, должны продвинуться влево; когда г = О, не может существовать ни одна такая запись, поскольку иечезср двигаться вправо.
Алгоритм, конечно, очень элегантен, но, к сожалению, нестабилен при наличии равных ключей. Он тесна связан с построением Фоаты в теореме 6.1.2В. РАЗДЕЛ 5.2.1 1. Да. Равные элементы никогда не меняются местами. 2. Да, но в случае, если имеются равные элементы, время работы увеличится и процесс сортировки будет выполняться в прямо противоположном направлении по сравнению с устойчивой сортировкой. 3. Предполагается, что следующая программа из 8 команд - — самая короткая программа сортировки для машины Н11, хотя она и не может быть рекомендована из-за низкой скорости выполнения. Считается, что числа находятся в ячейках 1,, )Ч [т. е. 1МРОТ ЕОО О); в противном случае нужна еще одна команда.
2Н 101 0.1 В СМРХ 1,1 В Л.Е 1Г В МОЧЕ 1,1 А 3ТХ 0,1 А 3ТХНТ ЕМТ1 М А + 1 1Н ОЕС1 1 В+ 1 11Р 23 В+1 ! 3амечанпе. Чтобы оценить времи выполнения, заметим, что А равяо числу инверсий. а величина  — довольно простая функция таблицы инверсий и [в предположении, что элементы ввода различны и расположены в случайном порндке) имеет производящую функцию ,я-з(1+ )(1 г г+з) з заг + з+гэз) (1 + к-з + гк — з + + я1к — зьгг)/дп СРеднее значение В Равно 1Т вЂ” 1 + 2 ~,(к — 1)(2к — 1)/6 = (1з' — 1)(419 + Н + 36)/36; следовательно, среднее время выпогпзения -- примерна 57Зг и.
г з 4. Рассмотрим таблицу инверсий Вз .. В,ч данной исходной пгрестаяовки в смысле упр. 5.1.1 -7. Величина А на единицу меньше числа элементов В,, которое равно 1' — 1, а В равно сумме элементов Вм Следовательно, абе неличины —  — А и  — достигают макСимума, когда исходная перестановка равна Х... 2 1, обе величины достигают минимума, когда исходная перестановка равна 1 2... Н.
Следовательно, минималыюе возможное время выполнения достигается при А = 0 и В = 0 и равно (107зг — 9) и; максимальное время выполнения будет достигнуто при А = Тзз — 1 н В = (~ ) и равно (4.5Нг + 2.5Л' — 6) и. 5. Искомая производящая функция равна произведению г ' и производящей функ!Оя — 9 ции для величины 9 — ЗА. Рассмотрен, как в предыдущем упражнении, таблицу инверсий и вспомнив, что отдельные элементы таблицы инверсий не зависят один от другого, находим искомую производящую функцию з' Пз«,к((1+ г +. + г ~ + г ' ' )/г). Дисперсия ранна 2.25Нз + 3.375 Л'~ — 32 6251т" + ЗОНк — ОНчы. 6. Организуйте область вывода как циклический список, в которои позиция Н будет соседней по отношению к позиции 1, Следующий элемент, который нужно вставить, берется с левого или правого конца текущей серии нерассортироеанных элементов в зависимости от тога, оказался ли предыдущий вставленный элемент соответственно спрана или слева от центра области рассортированных элементов.
В конце обычно требуется "прокрутить" эту область, переместив каждую запись на )г позиций па кругу, где й — - некоторое фиксированное значение. Это можно эффективно выполнить способом, аналогичным рассмотренному в упр. 1.3.3-34. 7. Среднее значение для )а, — Я равно срмчи1зУЯ по У, получим -(( з ) + ( з )) = з(гз 1). 8. НезТ рассмотрите, например, пос.ледовательность ключей 2 1 1 1 1 1 1 1 1 1 1. 9.
Для табл. 3 А = 3 + 0 + 2 + 1 = 6, В = 3 + 1 + 4 + 21 = 29; для табл. 4 .4 = 4+ 2+ 2+ 0 = 8, В = 4+ 3+ 8+ 10 = 25; следовательно, время выполнения программы В в этих двух случаях равно соответственно 786н и 734н. Хотя число перезаписей сократилось с 41 да 25, эта программа не мажет соперничать с программой Я па времени работы, поскольку при гз' = 16 тратится многа времени на вспомогательные операции, необходимые для организации четырех проходов.
При сортировке 16 элементов лучше выполнить только два просмотра. двухпроходный вариант программы П начинает превосходить по скорости программу Б примерно при Ж = 13, и все же на коротких наборах входных данных они почти равноценны (а при малых значениях Н, возможно, существенную роль играет длина программы) 10. Вставить "1НС1 1НРОТ, БТ1 ЗР(О:2)" между командами в строках 07 и 08 и заменить строки 10 17 следукзщими строками: ЗН СОРА 1НРНТ+Н-Н,1 ХТ вЂ” Я ЗСЕ ЗР 74Т вЂ” В За счет увеличения программы на четыре комшзды удается сэкономить 3(С-Т) машинных циклов, где С вЂ”. число случаев, когда К, ) К, з В табл. 3 и 4 экономия времени составляет соответствюшо около 87 и 88 циклов; эмпирически значение С/(74Т вЂ” 5) можно выбрать равным приблизительно О 4, если Ь,тз/Ь, 2 и приблизительно 0.3, если Н„т1/и, 3, так что это усовершенствование стоит затраченных усилий.
(С другой стороны, аналогичное изменение программы 5 нежелательно, так как зкономия в этом случае пропорциональна всего лишь 1ои Х, если только заранее неизвестно, что входные данные достаточно хорошо упорядочены.) 12. Замена ( символом ( всегда приводит к изменению количества инверсий на ю1 в зависимости от того, где выполнена замена — над нли под диагональю. 13. Припишите вес )з — 7) сегменту от (з, 7'-1) до (з, 1). 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
