AOP_Tom3 (1021738), страница 44
Текст из файла (страница 44)
[М41] (Бьерн Пунен (В1огп Роопеп).) (а) Докажите, чта существует константа с, такая, что если га из смещений Л, в алгоритме П имеют величину, меныпую Х/2, то время выполнения будет в худ»пем случае равно й(Ж~ '?м ). (Ь) Следовательно, время выполнения алгоритма П будет в худшем случае равно й(?з'(!о8?»/!об!обК) ) для всех последовательностей смещений. 28. [15] Какая из последовательностей смещений, указанных в табл. б, наилучшая для программы П с точки зрения суммарного времени выполнения сортировки? 20. [40] Найдите для?0 = 1000 и различных значений 1 эмпирические значения Л~ и..., Ли Ле, которые, быть может, минимизируют среднее число операций перемещения записей В,„, в алгоритме П. 30. [МХЗ] (В, Пратт (У, Ргаэе).) Покажите, что если множество смещений при сортировке методом Шелла есть (2"3 [ 2"3» <?з), то число проходов равно примерна -'(1обэ К)(1о8з Ж) и на каждый просмотр приходится ие более К/2 операций перестановки записей.
В действительности, если К. » > Км то на любом проходе Кз — з»,Кз-ы < Кз < К,-» Кз+», К,+ы; так что можно просто поменять местами К, » и К, и увеличить 1 на 2Л, сэкономив два сравнения в алгоритме О. (Указание. См, упр. 25.) ь 31. [25] Напишите йХХ-программу для алгоритма сортировки, предложенного Праттом (упр. 30). Выразите время ее выполнения через параметры Я, В, В, Т, ?У, аналогичные соответствующим параметрам в программе Б.
32. [10] Каково будет окончательное содержимое связей баул .. б»э, если провести до конца сортировку списка посредством вставок в табл. 8? ь 33. [25] Как усовершенствовать программу (» чтобы время ее выполнения определялось величиной 5В, а ие 7В, где В5 — число инверсий. Проанализируйте возможность подобного улучшения применительно к программе 8. 34. [М10] Проверьте формулу (14). 35. [21] Напишите йХХ-программу, которая должна выполняться после программы М и объединять все списки в единый список.
Созданная программа должна устанавливать поля 5138 точно так, как если бы они были заполнены программой Ь. 36. [18] Предположим, что размер байта компьютера ИХХ равен ста и значения шестнадцати ключей в табл. 8 равны 503000, 087000, 512000,, 703000. Определите время работы программ Ь и М с этими данными при М = 4. ЗТ. [Муб[ Пусть д (х) — производящая функция дли числа инверсий в случайной перестановке и элементов (ср. с формулой 5.1.1 — (11)).
Пусть длм(х) — соответствующая производящая функция для величины В в программе М. Покажите, что Млюл / гг гГ улм(х) г = ~' ув(х) л>э гг>Э и воспользуйтесь этой формулой для вывода дисперсии величины В, ЗЗ. [НМ22[ (Р. М. Карп (К. М, Катр).) Пусть Е(х) — некоторая функция распределения вероятностей, причем Е(0) = О и Е(1) = 1. Докажите, что если ключи Кг, Кэ,..., Км независимо выбираются случайным образом из последовательности чисел с этим распре- делением и М = сгг', где с — константа, а Ф -г сю, то время выполнения программы М есть О(?гг), если только Š— достаточно гладкая функция. (Ключ К вставляется в список г, если [МК) м / — 1; зто случается с вероятностью Е(у/М) — Е((/ — 1)/М).
В тексте раздела рассматривался лишь случай Е(х) = х, 0 < х < 1.) ЗО. [НМ1 б[ Если программа выполняется приблизительно за А/М+ В машинных циклов и использует С + М ячеек памяти, то при какам выборе ЛХ достигается минимальное значение произведения пространства памяти на время выполнения? э 40. [НМ24 [ Найдите выражение для асимптотической величины среднего числа максиму- мов слева направо (формула (15)), которое возникает при множестве вставок в список, если М =?гг/и для фиксированного а при Н -+ оо, Проанализируйте поведение абсолютной ошибки О(ггГ '), сформулировав ответ в терминах наказав>ельней оншегральнай функции Ег(х) = [ е 'г(1/й 41. [НМ2б) (а) Докажите, что сумма первых (") элементов в (10) равна О(р>в). (Ь) Теперь докажите теорему 1.
42. [НМ48[ Проанализируйте поведение усредненного показателя в ходе выполнения сор- тировки Шелла, если имеется Г = 3 смещений 5, д и 1 и полшается, что И .1. д, Очевидно, что на первом проходе при выполнении 5-сортировки получим в среднем -„'гг'~/5 + О(Х) перемещений записей. а) Докажите, что втоРой пРоход, д-соРтиРовка, даст хэ-(~/6 — 1/ч%)?О/У+ О(ЬН) пеРемещений записей. Ь) Докажите, чта третий проход, 1 сортировка, даст ф(5, у)гг1+О(2~5~) перемещений, где ° 43. [25[ В упр.
ЗЗ для ускоренного выполнения алгоритма Б используется прием„который делает ненужной проверку "г > О" на шаге 54. Этот фокус ие проходит в алгоритме О. Покажите, что, тем не менее, существует возможность избавиться ат проверки "г > 0" на шаге Р5, повысив тем самым скорость выполнения внутреннего цикла сортировки Шелла. 44. [М25[ Если гг = аг... а„и гг' = аг... а'„— суть перестановки множества (1,..., и) „ будем говорить, что л < л', если г-й наибольший элелгент в (аг,..., а.) меньше или равен г-му наибольшему элементу в (аг,...,а',) при 1 < г < г < и. (Другими словами, гг < л', если для всех 2 сортировка посредством простых вставок л является покомпонентно меньшей или равной сортировке посредством прямых вставок гг после того, как вставлены первые / элементов.) а) Если л находится "выше" л' в смысле, определенном в упр. 5.1.1 — 12, следует ли из этога, чта гг < гг'? Ь) Если л < гг', следует ли из этого, что ггл > гг'"? с) Если гг < гг', следует ли из этого, что я расположена выше л'? 5.2.2.
Обменная сортировка Мы подошли ка второму из семейств алгоритмов сортировки, упомянутых в самом начале раздела 5.2, — к методам обменов нли транспозиций, предусматривающих систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется. Реализацию метода прогтых вставок (алгоритм 5.2.15) можно рассматривать как обменную сортировку: берем новую зались 1с, и,по существу, меняем местами с соседями слева да тех пор, пока она не займет нужное место.
Следовательно, классификацию методов сортировки по таким семействам, как вставки, обмены, выбор и т. д., нельзя считать слишком строгай. В этом разделе рассматриваются четыре типа методов сортировки, для которых обмен является основной операцией: обменную сорепировку с выбором (метод пузырька), обменную сортировку со слиянием (параллельную сортировку Бэтчера), обменную соршировку с разделением (быструю сортировку Хоара) и поразрядную обменную сорглировку. Метод пузырька.
Пожалуй, наиболее очевидный способ обменной сортировки— сравнить К~ с Кю меняя местами Н~ и Вз, если их ключи расположены не в нужном порядке, и затем проделать то же самое с Яз и Вз, Вз и Вз и т. д. При выполнении этой последовательности операций записи с большими ключами будут продвигаться вправо; и действительно, все это закончится тем, что запись с наибалыпим ключом займет положение Лк.
При многократном выполнении данного процесса соответствующие записи попадут в позиции Вк ы Ям т и т. д., так что, в конце концов, все записи будут упорядочены. На рис. 14 показано использование этого метода сортировки для шестнадцати ключей: 503 087 512 ... 703. Последовательность чисел удобно представлять не горизонтально, а вертикально, чтобы запись Лк была в самом верху, а Н, — в самом низу. Метод назван "методом пузырька'; потому что большие элементы, подобно пузырькам, "всплывают" на соответствующую позицию в противоположность 'методу погружения" (т.
е. методу простых вставок), в котором элементы погружаются на соответствующий уровень. Метод пузырька известен и пад более прозаическими именами, такими как "обменная сортировка с выбором" н "метод распространения". Нетрудно видеть, что после каждого просмотра последовательности все записи, расположенные выше самой последней, которая участвовала в обмене, и сама эта запись должны занять свои окончательные позиции, так что нх не нужно проверять при последующих просмотрах. На рис.
14 процесс сортировки с этой точки зрения отмечен подчеркиванием последнего элемента, занявшего верную позицию. Обратите внимание, например, на та, чта восле четвертого прохода видно, что еще пять записей сразу заняли свои окончательные позиции. При последнем просмотре перемещения записей вообще не было. Теперь, понаблюдав за процессом, мы готовы сформулировать алгоритм.
Алгоритм В (Метод вузирька). Записи Яп..., Вк перекомпановываются в пределах того же пространства памяти; после завершения сортировки их ключи будут упорядочены так: К~ < ( Кк (рис. 15). В1. [Начальная установка ВООИВ.] Присвоить ВООИО <- Ж. (ВООИΠ— индекс самого верхнего элемента, о котором еще не известно, занял ли он свою окончательную о х х с а И и о х о 1 х о о Р о а ш со о х о о с х а ш о х о о Ы 703 , 908 765 ; 703 908 908 908 908 908 908 908 897 897 908 , 897 ; 703 765 677 897 897 897 765 703 897 765 897 677 ; 765 612 ' 677 509 ' 612 765 703 765 703 677 765 765 765 703 703 703 703 677 677 677 677 677 677 154 509 ' 612 , 653 653 653 653 653 653 653 612 612 512 612 512 512 э09 503 509 509 503 503 154 г' 426 426 154 275 эФ' 170 087 426 275 154 170 275 170 170 154 154 170 087 087 061 087 087 061 061 061 061 Рис.
14. Процесс сортировки методом пузырька. позицикб таким образом, можно отметить, что в начале сортировки еще ничего не известно о порядке размещения записей.) В2. [Цикл по ~.) Присвоить 1 +- О. Выполнить шаг ВЗ при 7' = 1, 2, ..., ВООвΠ— 1. Затем перейти к шагу В4. (Если ВООйО = 1, то сразу перейти к В4.) ВЗ. [Сравнение/обмен Л,: Вз ч.) Если К1 > Кз,.ы то поменять местами 773 4+ 711зы и установить г 4 — ~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
