Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 29
Текст из файла (страница 29)
8? ь ЗЗ. [35) Как усоверппшствовать программу 1., чтобы время ее выполнения определялось величиной 5В, а не 7В, где В5 — число инверсий. Проанализируйте возможность подобного улучшения прпменительно к программе Б. 34. [М10) Проверьте формулу (14). 33. [31[ Напишите НХХ-программу, которая должна выполняться после программы М и объединять все списки в единый список.
Созданная программа должна устанавливать поля ЕХЗХ точно так, как если бы они были заполнены программой Ь. 36. [18[ Предположим, что размер байта компьютера ИХХ равен ста и значения щестна- дцатя ключей в табл. 8 равны 503000, 087000, 512000,..., 703000. Определите время работы программ О и Ы с этими даннымн прн М = 4, 37, (Мдд] Пусть д„(г) — пронзэодящэл функция для числа инверсий в случайггой перестановке и элементоэ (ср. с формулой 5.1.1-(1!)). Пусть длм(э) — соответствуюшая производящая функция для величины В в программе Ы.
Покажите, что Мигел / «|' дкм(з) = ~~' д«(г) Ф>е «йе и воспользуйтесь этой формулой для вывода дисперсии величины В. 33. ]НМду] (Р. Ы. Карп (11. Ы. Катр).) Пусть Р(з) — некоторая функция распределения вероятностей, причем К(0) = Р и Р(1) = 1. Докажите, что если ключи КмКт,,Кл независимо выбираются случайным образом нз последовательности чисел с этим распределением и М = сЬГ, где с — константа, а Ф -г оо, то время выполнения программы Ы есть 0(Ф), если только Р— достаточно гладкая функция.
(Ключ Х вставляется в список /Ь если (МК] = у — 1; это случается с вероятностью Щ/М) — Г((у — 1)/М). В тексте раздела рассматриэался лишь случай Р(х) ж х, 0 < х < 1.) 39. ]НМИ] Если программа эыполняетгя приблизительно за А/ЛХ+ В машинных циклов и использует С + М ячеек памяти, то при каком выборе М достигается минимальное значение произведения пространства памяти на время вьпюлнения? ь 40. ]НМЦ] Найдите выражение для асимптотической величины среднего числа максимумов слева направо (формула (15)), которое возникает при множестве вставок в список, есин М = Ф/а для фиксироэанного а при Ьг ~ оо. Проанализируйте поведение абсолютной ошибки О(Ф г), сформулировав ответ в терминах гюкаэаявельной нитеграэьной функции Ег(э) = ];~е 'й/й 41.
(НМдд] (а) Докыкнте, что сумма первых (э) элементов в (10) равна 0(рэ*). (Ъ) Теперь докажите теорему 1. 42. [НМ4У] Проанализируйте цоведение усредненного показателя я ходе выполнения сортировки Шелла, если имеется 1 = 3 смещений Ь, д и 1 и полагается, что Ь Ъ д. Очеаидно, что на первом проходе при выполнении Ь-сортировки пахучим э среднем 1Ьгэ/Ь + 0(ЬГ) перемещений записей. а) Докажите, что в юрой проход, д-сортировка, даст ф (Л вЂ” 1/4Ь ) (г/д + 0(ЬЖ) перемещений записей. Ъ) Докажите, что третий проход, 1 сортировка, даст гд(Ь, д) ЬГ+ О(деЬэ) перемещений, где "' ы4К~~",')(,"-)'~ -6)" "! -Й! э 43. (33] В уар.
ЗЗ дзя ускоренного вытголнения алгоритма 8 используется прием, который делает ненузхной проверку "1 > 0" на шаге 84. Этот фокус не проходит в алгоритме Э. Покажите, что, тем не менее, существует возможность избаэиться от проверки "г > 0«на шаге Рб, повысив тем самым скорость выполнения внутреннего цикла сортировки Шелла.
44. (МЖ] Если я = аг... а„и я' = а',... а'„— суть перестановки множества (1,..., «), будем говорить, что т < т', если 1-й наибольший элемент э (а„..., а ) меньше или равен 1-му наибольшему элементу э (а'„...,а]) при 1 < 1 < / < и. (Другими словами, я < э.', если для всех у сортировка посредством простых зстаэок л является покомпонентно меньшей или равной сортировке посредством прямых вставок э' после того, как встаалены первые / элементов.) а) Если я находится "выше" я' в смысле, определенном в упр. 5.1.1-12, следует ли из этого, что х < я'? Ъ) Если л < я', следует ли из этого, что я" > э"'"? с) Если х < к', следует лн из этого, что х расположена выше я'? 5.2.2. Обменная сортировка Мы подошли ко второму из семейств алгоритмов сортировки, упомянутых в самом начале раздела 5.2, — к методам обменов илн транспознций, предусматривающих систематический обмен местами между элементамн пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется.
Реализацию метода простых вставок (алгоритм 5.2.15) можно рассматривать как обменную сортировку: берем новую зались В и, по существу, меняем местами с соседями слева до тех пор, пока она не займет нужное место. Следовательно, классификацию методов сортировки по таким семействам, как вставки, обмены, выбор и т. д., нельзя считать слишком строгой. В этом разделе рассматриваются четыре типа методов сортировки, для которых обмен является основной операцией: обменную сортировку с амбаром (метод пузырька), обменную сортировку со слиянием (параллельную сортировку Вэтчера), обменную сортировку с разделением (быструю сортировку Хоара) и поразрядную обменную сортировку.
Метод пузырька. Пожалуй, наиболее очевидный способ обменной сортировки— сравнить К» с Кз, менян местами В~ и Вз, если их ключи расположены не в нужном порядке„и затем проделать то же самое с Вз и Вз, Вз н В» и т. д. При выполнении этой последовательности операций записи с большими ключами будут продвигаться вправо; н действительно, все это закончится тем, что запись с наибольшим ключом займет положение Ву.
При многократном выполнении данного процесса соответствующие записи попадут в позиции Вм ы Вк з и т. д., так что, в конце концов, все записи будут упорядочены. На рис. 14 показано использование этого метода сортировки для шестнадцати ключей: 503 087 512 ... 703. Последовательность чисел удобно представлять не горизонтально„а вертикально, чтобы запись Вк была в самом верху, а В» — в самом низу. Метод назван их»егодом пузырька", потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию в противоположность "методу погружения" (т.
е. методу простых вставок), в котором элементы погрунаиотся на соответствующий уровень. Метод пузырька известен и под более прозаическими именами, такими квк "обменная сортировка с выбором" и "метод распространения". Нетрудно видеть, что после каждого просмотра последовательности все записи, расположенные выше самой последней, которая участвовала в обмене, н сама эта запись должны занять свои окончательные позиции„так что их не нужно проверять при последующих просмотрах. На рнс.
14 процесс сортировки с этой точки зрения отмечен подчеркиванием последнего элемента, занявшего верную позицию. Обратите внимание, например, на то, что после четвертого прохода видно, что еще пять записей сразу занялн свои окончательные позиции. Прн последнем просмотре перемещения записей вообще не было. Теперь, понаблюдав за процессом, мы готовы сформулировать алгоритм, Алгоритм В (Метод пузырька). Записи В„..., Вк перекомпоновываются в пределах того же пространства памяти; после завершения сортировки их ключи будут упорядочены так: К» « Ки (рнс. 15).
В1. [Начальная установка ВООИР.) Присвоить ВООИР +- Х (ВООИР— индекс самого верхнего элемента, о котором еще не известно, занял ли он свою окончательную о оч ко й 275 897 ю 170 р 512 а~в 061 503,1 087 Рис. 14. Процесс сортировки методом пузырька. позицию; таким образом, можпо отметить, что н начале сортировки еще пичего Nе известно о порядке размещения записей.) В2.
1Цвкл по 2.] Присвоить 1 с- О. Выполнить шаг ВЗ при 7' = 1, 2, ..., ВООВΠ— 1. Затем перейти к шагу В4. (Если ВООИО = 1, то сразу перейти к В4,) ВЗ. [Сравнеииеробмеп Яр: Кр„.~.) Если К, > Кр+ы то поменять местами Вр. еь Я +1 и усшновить 1+- 7', В4, 1Выли ли обмены?) Если 1 = О, завершить выполнение процедуры. В противном случае присвоить ВОШЮ+- 1 и возвратиться к шагу В2. $ Рис.
16. Блок-схема сортировки методом пузырька. 703 765 677 612 * 509 154 426 65З .' 275 897 170,' 908 Р 061 О87 503-Р" 908 703 765 677 612 509 а 426 65З ° ОО8 897 703 765 е' 677 612 5ОО 154 1 426 ббз Р' 275 17О 5ОЗ 061 087 «Ф~ ОО8 897 765 703 677 653 612 509 154 426 512 е 275 503 ьрг 170 087 оа 908 897 765 7ОЗ 677 653 612 Ы2 509 154 426 е 503.Р 275 170 087 061 908 897 765 70З 677 65З 612 512 509 5ОЗ 154 426.~Р 275 170 087 оа 908 897 765 703 677 653 612 Ы2 509 5ОЗ 426 154 275/ 170 087 оа 908 897 765 703 677 653 612 512 5ОО 5ОЗ 426 275 154 170 О87 оа 908 908 897 897 765 765 703 703 677 677 653 653 612 612 512 512 509 509 5ОЗ 5ОЗ 426 426 275 275 170 170 154 154 087 087 оа оа Программа В (Метод пузырька). Как н в предыдущих М1Х-программах этой гла- вы, полагаем, что сортируемые записи находятся в ячейках от 1ИРОТ+1 до 1ИРОТ+М.
гП:= 1; г12 тв !. 01 зтйнт еит1 и 00 1н зт1 воаио(1:г) ду Ейт2 1 04 Еит1 о 05 ЗИР ВООМО Об ЗН 1.0А 1ИРОТ,2 07 СИРА 1ИРОТ+1,2 ОО 11Е гр ОУ 1ОХ 1ИРОТ+1„2 10 ЗТХ 1ИРОТ,2 11 ЗТА 1ИРОТ+1,2 Ы ЕИТ1 0,2 и гн 1исг 1 Ц ВООИО ЕИТХ -ь„2 15 ЛХИ ЗВ 1б 4Н 51Р 1В 1 .4 А А А С С С нет обмена, если К» < К»+», В Вь!  — В,. В (Прежнее В,) -! В»+!. В Ф ь-у. С 5+- 5+1, А + С гХ +- Х вЂ” ВООИО.
[54однфнцнруемая команда) А+ С Выполнять шаг ВЗ дпя г 1 < 1 < ВО%В. А В4. Нет ебмепову Перейти к шагу В2, если1>0. $ В1. Ипп! апнзн вать ВООИО. 8+- 5». ЗООИО +- а В2. Янкл пп !', 1+-!. «- О. Выход, если у > ВООИО. ВЗ. С зацепив н нлн обмен В ! В, +~ Анализ метода пузырька. Очень полезно исследовать время работы алгоритма В. Оно определяется тремя яараметрами! числом проходов А, чнслом обменов В и числом сравнений С. Если нсходные ключи разлнчны и расположены в случайном порядке, можно предположит!и что онн образуют случайную перестановку множества (1,2,..., п). Понятие таблица инверсий (раздел 5,1.1) приводит к простому способу описания эффекта, достигаемого на каждом проходе при сортировке методом пузырька, Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
