Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 70
Текст из файла (страница 70)
Если К, = К,и у < (, то, в конце концов, В, окажется после В,. Кроме того, внесенные изменения замедлят работу программы С. 4, ЕИТ1 И 1 ЬТА ООП%Т+1,2 Ф !02 СООИТ,1 Х ОЕС! ! Н (.ОА ТИРОТ,1 Ж 2!Р е-4 )(г $ 5. Время выполнения уменьшится на А+ 1 — Ж вЂ” В машинных циклов, и это почти всегда можно рассматривать как существенное улучшение.
6. в =-О, е =-9.. После 1)1 После [)2 После [)4 Во время [)5 0 О 0 2 2 1 2 4 о 2 3 5 0 0 0 0 0 0 О О 1 3 3 2 1 1 5 6 9 12 14 15 16 5 5 8 91215 16 г'=8 1С вЂ” 4А — — 5! 6А 6Т 61 70 7И вЂ” -" 1С 2Е 4А ЬТ 50 51 6А 6Т 61 70 7И 85 9 СООИТ = СОСЕТ = СООИТ .=- СООИТ = ООТРОТ = ООТРОТ ~ После ))5 ОС 00 !И 7. Да; обратите внимание на то, что СООИТ[К.) уменьшено на шаге [)6, а затем уменьшаетсн у. 8. Сортировка будет выполняться, но не будет устойчивой (см.
упр, 7). 9. Пусть М = е — з; будем считать, что ]к] и ]е] умещаются в два байта. 1ЛС(В1) ш 1ИРОТ+2; ЬОС(СООИТ[У)) ш СОСЕТ+)'; 10С(Я)) Ш ООТРОТ+)'; гП ш (; г12 ш), г13 ш 1 — ч илн НЗшК, И ЕОО Т-О ЕЕТ ЕОО 0:2 (Сопутствующая информация в байтах 3: 5) и = 9 и имеется цикл (Ол 1с Ос Зл 7л Зс 1л 2с Ьс 4л). Этот цикл появляется в мультиграфе тогда и только тогда, когда перестановка со знаком начинается с 4 и содержит подцепочкн 9187 и 25 или нх реверсы.
Все решения можно получить, если найти все перестановки со знаком множества (1,2,3,6) и заменить 1 значениеи 9187, 2 — значением 25, Значит, Есь < )г(25)2г(я+1)А2" ь(я — А)1/2"и! = 1(1(Ь+ 1/(и+ 1 — Ь)), Из этого следует, что Ес = 2 „" ., Есь + Ес +1 < Н + 1. Поскольку и+ 1 — с — нижняя граница числа перебрасываний, нам понадобится > и+ 1 — Ес > и — Н из них. ]В этом доказательстве использована идея В. Бафиа (Ъ'. Ва[ва) и П. Певзнера (Р. Речипег), ЯСОМР 25 (1996), 272-289, которые изучали боле» сложную проблему сортировки перестановки без знака посредством реверсирования. В этой задаче рассматривалнсь перестановки, которые могут быть записаны в виде произведения неразрезанных циклов (1 2 3) (3 4 5)(5 6 7)..., оканчивающихся либо на (и-1 и), либо на (и — 2 и — 1 и) в зависимости от того, каким является и: четным нли нечетныы.
Оказалось, что такие перестановки трулнее всего сортировать.] 10 ЕИИЗ Н 1 РЕЯ ЗТЕ СОСЕТ+Т,З М + 1 СОСЕТ[о — Л) у- О, ТИСЗ 1 И+1 узм М+1 о<1<о. 2Н ЕИТ2 И 1 я2,лл, ЗН 1.03 ХЕРСТ,2(НЕТ) К [)3. Увеличить СООИТ К 10А сааит,з уу ТИСА 1 УМ зта сааит.з ут ОЕС2 1 АУ ЛР ЗВ А' А >у>а. ЕИИЗ И-1 1 В4. НИИоупуешге. 10А СОСЕТ+О 1 гА е- СООИТ[1 — 1). 4Н Ааа СООМТ+7 ~ 3 М СООМТ П вЂ” 1) + СООМТ [П МТА с00мт+7,3 М -+ со(умт[П. ТМСЗ 1 М АЗЕР 4В М бн емтз м 1 ен |аз ТМРОТ,2(Нет) А' (Л)1 СООИТ, З х 1+- 000ит[ку). 00А 1МРОТ,2 УМ гА +- У1,. ИТА оатрат,1 Х Яу е — гА. ОЕС1 1 А' вт1 сааит,з А' СОНЕТ[К)) +-1 — 1. ОЕС2 1 УМ ЛР б» Х У>у>а.
3 Время выполнения — (1ОМ + 22АУ + 10) н. 10, Чтобы не использовать дополнительно Ут' бит для "маркера" (см. раздел 1.3.3 и Су- Ьепуейсэ 1 (1063), 95) и при этом все-таки оставить время выполнения пропорциональным К, можно использовать слелующий алгоритм, основанный на циклической структуре пе- рестановки. и<1< о. Щ. Выкай Дз, В1. Присвоить А <- р(у). Вз, Если А > у, присвоить Уг +- р(А) и повторить этот шаг.
ВЗ. Если Й < у) ничего не выполнять, ио если А = ( (зто означает, что ( — нанмельшее в своем цикле), то переставить операции цикла, связанные с( следующим образом. Р1. (Цикл по и.] Выполнить шаг Р2 для 1 < 1 < гУ; затем завершить выполнение процедуры. Рз. (р(У) = (У) Выполнить шаги с РЗ по Р5, если р(у);А А РЗ. [Начвло цикла.) Присвоить У +- Л„у' у- (, Р4. (Обработать Ут,.) Присвоить А +- р(у), У(у +- Яы р(Я +- у, у' +- А, Если р(у) р' у, повторить этот шаг.
РЬ. (Конец цикла.) Присвоить Еу +- Г, р(у) +- у. М Этот алгоритм изменяет р(1), поскольку в приложениях, использующих сортировку, можно считать, что р(у) хранится в оперативной памяти. С другой стороны, существуют прило- жения, такие как транспоннрование матриц„в которьух р(у) является функцией у, т. е. е о для зкономии памяти необходимо вычислять, а не считывать вз таблицы, В этом случае можно использовать следующий метод, выполняя шаги от В1 до ВЗ для 1 < ( < у)у. Присвоить ( +- Л,; затем, пока р(й) ф й повторять присвоения Вг +- Лр(ю и й +- р(й); и, наконец«присвоить Л«е- ( $ Этот алгоритм аналогичен процедуре, описанной в работе Л.
Васс)поуб, Сошр. Х 10 (1967) « 310,но требует меньшего количества операций перемещения даиньгх; несколько усовершенствованный алгоритм преджакил И. Д. Г. Мак-Леод (1. О. С. Мас) еой) (Аизгга)«вл Сагир. 3. 2 (1970), 16-19), Анализ, выполненный для случайной перестановки в упр. 1.3.3-14, показывает, что шаг В2 выполняется в среднем (А«+ ЦНл — ««' рэл. (См.
также ссылки иа литературу в ответе к упр. 1.3.3-12.) Аналогичный влпзритм можно разработать и для того, чтобы заменить (Лр(,р ..,, Вр(л) ) иа (Вц..., Лл), например, если перекомпановка в упр. 4 должна быть выполнена при условии ООТРОТ = 1ИРОТ. 11. Пусть г11ж Л г12 ау«г13на й; гХ ш К 1Н ЕИТ1 И «и кя«е' ЗН СНР1 Р,1 «««, «Ы=- 1Е 8Р Ж Перейти, если р(1) = 1.
я «я «я~. А — ««~«. н . «. ЕИТ2 0,1 А — В у+-й 4Нй03 Р,2 А( — А Р. ики в ь .й+-р(у). 1.Рй 1ИРОТ,З ««( — А ЗТа 1ИРОТ„2 Ю вЂ” А Л) +- Вь. ЗТ2 Р,2 «'«' — А р()) е- )1 ЕИТ2 0,3 Ю вЂ” А у+- й. СИР1 Р,2 А( — А 1ИЕ 4З )«' — А Повторить, если р(у) ~ й ЗН ЗТК 1ИРОТ,2 А — В РБ. ~не НН((Н.„В) +- Ф. ЗТ2 Р.2 А — В р(у') е- 11 ЗН РЕС1 1 А« 51Р 26 А«ХВ(>1. ! Время выполнения равно (17А' — ЗА — 7В+ Цв, где А — числа циклов в перестановке р(Ц... Р(А«) и  — число неподвижных точек перестановки (единичных циклов).
Получнм \ ( ' «, Я, «',««Я -~Н) «=( ' «, 1, ««Ц для Аг > 2 в соответствии с 1.3.3-(2Ц и 1,3.3-(28). 12. Очевидный способ — пройти по всему списку, заменим связи й-го элемента числом й, и затем перекомпоновать элементы на втором проходе. Описанный ниже более пряъюй и быстрый способ для случая, когда записи не слишком велики, принадлежит М. Д. МакЛареиу (М. В. МасЬэгеп).
(Для удобства предполагается, что 0 < ЫИК(Р) < Р«' при 1 < Р < А", где А ьз О.) М1. (Инициализация,) Присвоить Р+- НЕАР, й <- 1. М2. [Вьпюлнено7) Если Р = А (или, что равносильно, если й = Х + Ц, выполнение процедуры заканчивается. МЗ. (Обеспечить Р > й.) Если Р < й, присвоить Р е- 11ИК(Р) и повторить этот шаг.
Ма. (Обмен.] Поменять местами Ль и Л(Р). (Предполагается, что 1.1ИК(й) и ьТИК(Р) также при этом меняются местами,) Затем присвоить О е- ь?ИК(й), 11ИК(й) +- Р, Р+-О, й е- й+1 и вернуться к шшу М2. 3 Доказательство состоятельности метода М. Д. Мак-Ларена может базироваться на проверке по индукции следующего свойства, которое всегда выполняется перед пачвлом шага М2: элементы, которые > й в последовательности Р,ь1ИК(Р),ь1ИК(ь|ИК(Р)), ..., А, — это ап аэ...., ая~~-ю где В~ < .. < Вь-~ < Ла, < < Л я,, „— требуемый окончательный порядок записей. Далее, ЫМК(у) > ) для 1 < ) < а, так что из равенства ЫИК()) = Л следует ) > й.
Довольно нптересяо проанвлизировать алгоритм М. Д. Мак-Ларена. Одно из его замечательных свойств состоит в том, что алгоритм можно выполнить в обратном поряд- ке н восстановить исходное множество связей из конечных значений 11МК(1) ... ЫИК(Ж) .
Каждая из В! возможных конфигураций иа вьссоде при ) < ЫИК()) < Х соответствует в точности одной из К! возможных конфигурэший на входе. Если обозначить через А количество операций Р э- 1.1ИК(Р) на шаге МЗ, то К вЂ” А — - число индексов ), таких, что ЫИК(э) = у после завершения выполнения процедуры. Зто возникает тогда и только тогда, когда ) наибольшее в своем цикле; следовательно, Х- А равно числу циклов перестановки, а А = (пйпО, ате )т' — Ня, шах Ю-1). См. М.
(). МасЬагеп, )АСМ 13 (1966), 404-411; Р. Сг1еэ, 1. Р, Ргшз, Ес)елее оГСошриэег РгобташпнлИ 8 (1987), 139-145. 13. ПЬ', Присвоить г +- Х, К)б'. Если г = О, остановиться. В противном случае, если СООИТ[К„) < г, присвоить г +- г — 1 и повторить этот шаг; если СОСЕТ(К,) = г, умеяьшить и СООИТ(К„), и г на 1 и повторить этот шаг. В противном случае присвоить Л э- В,,у +- СООМТ(К„), СООМТ(К ) +- у — 1. ПТ'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
