Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 23
Текст из файла (страница 23)
Ясно, что А равно числу случаев, когда Кг С ппп(К|,...,К ~) при 1 < у ( Х, т. е. это число левосторонних минимумов — величина, которая была подробно проанализирована в разделе 1.2.10. Нетрудно прийти к выводу, что Н тоже известно: число перемещений записей при фиксированном / равно числу инверсий ключа Кй, так что Н равно числу инверсий перестановки К~ Кз... Ля.
Следовательно, согласно формулам 1.2.10-(16), 5.1.1-(12) и 5,1,1 — (13) имеем А = (пппО, ауе Нл — 1, гпах Х вЂ” 1, г)еу Ня — ' Нгг ), 00 з=<-,-.~ь'-кг4. М-пуз - тТю-нГг+ я~6>, а среднее время выполнения программы Б в случае, если ключи различны и рас- положены в случайном порядке, равно (2.25Х + 7.75Х вЂ” ЗНл — 6)и. В упр. 33 показано, как можно несколько повьюить скорость. Приведенные в качестве примера в табл. 1 данные содержат 16 элементов; в наборе имеется два левосторонних минимума„087 и 061, и, как было показано в предыдущем разделе, 41 инверсия.
Следовательно, Н = 16, А = 2, В = 41, а общее время сортировки равно 514и. Бинарные и двухпутевые вставки, Когда при сортировке методом простых вставок обрабатывается у-я запись, ее ключ сравнивается в среднем примерно с у/2 ранее рассортированных ключей; поэтому общее число сравнений равно приблизительно (1 + 2 + - + Ю)/2 г"'з/4, а это очень много, даже если Ф не так уж и велико.
В разделе 6.2.1 будут проанализированы методы бинарного поиска, которые указывают, куда вставлять у-й элемент после приблизительно 161 операций сравнения с соответствующим образом выбранными элементами сортируемого набора. Например, если вставляется 64-я запись, можно сначала сравнить ключ Кы с Кзз, а затем, если он меньше, сравнить его с Кгк, если больше — с Коз и т. д., так что место для Воз будет найдено после всего лишь шести сравнений. Общее число сравнений для Х вставляемых элементов равно приблизительно Ф 16 Л, что существенно лучше, чем 1Фз; в разделе 6.2.1 показано, что соответствующая программа не обязатеяьно намного сложнее, чем программа для простых вставок.
Этот метод называется методом бинарных есгпаеок. Он упоминался Джоном Мочлн (ЗоЬп МапсЫу) еще в 1946 году, в первой публикации по машинной сортировке. Неприятность состоит в том, что метод бинарных вставок позволяет решить задачу только наполовину: после того как найдено место, куда вставлять запись Вй, все равно нужно подвинуть примерно зу ранее рассортированных записей, чтобы освободить место для Вз-, так что общее время выполнения остается, по существу, пропорциональным Хз.
В некоторых компьютерах (например, в 1ВМ 705) используются процессоры, в наборе команд которых имеется и команда перемещения блока памяти, выполняемая аппаратно с большой скоростью. Но с ростом Ф зависимость от Фз, в конце концов, начинает преобладать. Например, анализ, проведенный ь П орнгннзде автор использует термин "опц" — едкннпа, под которой подразумевается среднее время зыполноння одной ыыпкнной команды (см.
том!). Это н есть не что иное, ккк дднтеяьяость нмпннного пнкяь. — Ириы. перов. Таблица 2 ПРОЦЕСС СОРТИРОВКИ МЕТОДОМ ДВУХПУТЕВЫХ ВСТАВОК 503 503 503 512 503 512„ 503 512 908 503 512„903 503 512 897 908 503 512 397 908 087 л 061 087 061 037„ 061 087 170 061 087 170„ 061 087 170 275 Метод Шелла. Для алгоритма сортировки, который каждый раз перемещает запись только иа одну позицию, среднее время выполнения будет в лучшем случае пропорционально Фх, потому что в процессе сортировки каждая запись должна пройти в среднем через -'Ф позиций (см.
Упр. 7). Поэтому, если желательно получить метод, существенно превосходящий по скорости метод простых вставок, необходим механизм, с помощью которого записи могли бы перемещаться болыпими скачками, а не короткими шажкамн. Такой метод предложен в 1959 году Дональдом Л. Шеллом 1Попа1д 1. Зйей, САСМ 2, 7 (Зп1У, 1959), 30-32) и известен во всем мире под именем своего автора. Б табл. 3 проиллюстрирована общая идея, которая лежит в его основе.
Сначала делим 16 записей на 8 групп подав записи в каждой группе: (Вм Ве) (Вх, Вш) (Вв, Вы) Н результате сортировки каждой группы записей по отдельности приходим ко второй строке табл. 3. Этот процесс называется первым проходом. Обратите внимание иа то, что элементы 154 и 512 поменялись местами, а 908 и 897 переместились вправо. Разделим теперь записи иа четыре группы по четыре в каждой: (Вы Вь, Вр, Вгз),, (В4, Вэ, Вмь Вы). Затем опять рассортируем каждую группу в отдельности; результат этого второго прохода показан в третьей строке таблицы. На Х. Нэглером (Н. Ва81ег, САСМ 3 (1960), 618-620), показывает, что метод бинарных всхавок не рекомендуется использовать при сортировке более Ф = 128 записей по 80 символов на компьютере 1ВМ 705.
Методика анализа применима и к другим компьютерам. Разумеется, изобретательный программист может придумать какие-нибудь способы, позволяющие сократить число необходимых переписей в памяти; первый такой прием, предложенный в начале 50-х годов, проиллюстрирован в табл. 2. Здесь первый элемент помещается в середину области вьпода и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом удается сэкономить примерно половину времени работы по сравнению с использованием метода простых вставок за счет некоторого усложнения программы.
Можно применять этот метод, используя не больше памяти, чем требуется для Ф записей (см. Упр. 6), но мы не сханем дольше задерживаться на таких "двухпутевых" вставках, так как разработаны и горазда более интересные методы. Таблица 3 СОРТИРОВКА ШЕЛЛА СО СМЕШЕНИЯМИ В, 4, 2, 1 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 Сортировка через 8: 503 087 154 061 612 170 765 275 653 426 512 509 908 677 897 703 Сортировка через 4: 503 087 154 061 612 170 512 275 653 426 765 509 908 677 897 703 Сортировка через 2: 154 061 503 087 512 170 612 275 653 426 765 509 897 677 908 703 Сортировка через 1: 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 третьем проходе сортнруются две группы по восемь записей, "процесс завершается четвертым проходом, во время которого сортируютгя все 16 записей.
В каждой из промежуточных стадий сортировки участвуют либо сравнительно короткие массивы, либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок и сортировка выполняется довольно быстро. Метод сортировки Шелла также известен под именем 8пе1)эогФ и метода сортировки с "убывающим смещением", поскольку каждый проход характеризуется смещением Ь, таким, что сортируются записи, каждая иэ которых отстоит от предыдущей на Ь позиций, Последовательность значений смещений 8, 4, 2, 1 не следует считать незыблемой; можно пользоваться любой последовательностью Ьз з, Ьз т, ..., Ье, ио последнее смещение Ье должно быть равно 1.
Например, в табл. 4 продемонстрирована сортировка тех же данных со смещениями 7, 5, 3, 1. Как будет показано ниже, выбор значений смещений на последовательных проходах имеет весьма существенное значение для скорости сортировки. Алгоритм 0 [Сортлировка Шелла). Записи Вз, ..., Вя перекомпоновываются в том же адресном пространстве памяти. После завершения сортировки их ключи будут упорядочены: Кз « ° - ° Кзт. Для управления процессом сортировки используется вспомогательная последовательность смещений Ьз з, Ьз т, ..., Ье, где Ье —— 1; правильно выбрав эти значения в последовательности, можно значительно сократить время сортировки.
При 1 = 1 этот алгоритм сводится к алгоритму 8. 01. [Цикл по э.) Выполнить шаг 02 при э = 1 — 1, 1 — 2, ..., О, после чего завершить процедуру. 02. [Цикл по 7'.) Присвоить Ь з- Ь, и выполнить шаги от 03 до 06 при Ь < 7' < зТ. (Для сортировки элементов, отстоящих один от другого на Ь позиций, воспользуемся методом простых вставок и в результате получим К; < Кз.~ь для 1 < з < Ф вЂ” Ь.
Шаги от 03 до 06, по существу, такие же, как соответственно от 82 до 85 в алгоритме 8.) 113. [Установка з, К, В.) Присвоить з з- у — Ь, К +- К, В +- В . 04. [Сравнение К: К;.) Если К ) Кп то перейти к шагу 06. Таблица 4 СОРТИРОВКА ШЕЛЛА СО СМЕШЕНИЯМИ 7, 5, 3, 1 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 Сортировка через 7: 275 087 426 061 509 170 677 503 653 512 154 908 612 897 765 703 Сортировка через 5: И4 087 426 061 509 170 677 503 65З 512 275 908 612 897 765 70З Сортировка через 3: 061 087 170 154 275 426 512 503 653 612 509 765 677 897 908 703 Сортировка через 1: 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Об.
(Перемещение Вп уменьшение 1.) Присвоить В;~ьь +- ~, затем (+- 1 — Ь. Если 1 > О, то возвратиться к шагу В4. ХЭВ. (Перемещение В на место Вс[.ь.) Присвоить В;+и +- В. $ Соответствующая программа для МХХ не намного длиннее, чем наша программа для метода простых вставок. Строки 08-19 втой программы перенесены из программы б в более общий контекст алгоритма В. Программа О (Соргпироека Шелла). Предполагается, что смешения для сорти- ровки хранятся во вспомогательной таблице и Ь„находится по адресу Н + з; все смещения сортировки меньше Ф. Содержимое регистров таково: г11 щ,) — Ь7; г12 аз (; гА Рд В ьз К; г13 55 з; г14 гв Ь. Обратите внимание на то, что зта программа сама себя изменяет.
Это сделано для того, чтобы добиться более зффективного выполнения внутреннего цикла. 01 ЗТАВТ ЕМТЗ 7-1 08 1Н Ы4 Н,З с2. [[~ с ь 03 ЕМТ1 1МРОТ>4 Модификация адресов в трех 04 871 5 (О:2) командах основного цикла. 05 ЗТ1 бр(0:2) 06 ЕММ1 -М,4 гП +- Л' — Ь. 07 ВТ1 ЗР(0:2) 08 ЕМТ1 1-М,4 09 2Н (.ОА 1МРОТ+М,1 1О ЗН ЕМТ2 М-Н,1 11 4Н СМРА 1МРОТ„2 И ЭОЕ бр И ЕОХ 1МРУТ,2 Ц ВН ВТХ 1МРОТ+Н,2 И ОЕС2 0,4 16 32Р 4В 17 6Н ЗТА 1МРОТ+Н,2 И 7Н 1МС1 1 19 11МР 2В 80 ОЕСЗ 1 81 3ЗММ 1В 1>з>0. 1 1 Т Т Т Т Т Т Ь'Т вЂ” Я 17Т вЂ” Я В+ЖТ-Я-А В+г[Т-Я-А В В В В 1[7Т вЂ” Я 1+- 5+ 1.
Вз. П ясвонгы К В. 1 с- 1 — Ь. (Изменяемая команда) В4.(~юапь К [ Л~,, Перейти к шагу Вб, если К > Кь В5. Пе и сатьВ и. ьшять(. В'+с +- И. (14зменяемвя команда) 1~-1- Ь, Перейти к шагу В4, если 1 > О. [в,в~~ х [и 1 <- 1 + 1. Перейти к шагу Вз, если 1 < Ь[. «Анализ метода Шелла. Для рационального выбора последовательности значений смещений сортировки Ь~ и..., Ье для алгоритма 0 нужно проанализировать время выполнения как функцию от этих смещений.
Такой анализ приводит к постановке очень красивых, но еще не до конца решенных математических задач; никому до сих пор не удалось найти наилучшую возможную последовательность смещений для больших Х. Тем ие менее известно довольно много интересных свойств сортировки методом Шелла с убывающим смещением, н мы здесь их кратко изложим; подробности будут рассмотрены в приведенных ниже упражнениях. 1Читателям, не склонным к пространным математическим выкладкам, лучше пропустить следующие несколько страниц вплоть до начала обсуждения метода вставки в список, который следует эа формулой (12).) Счетчики частот выполнении в программе 0 показывают, что на время выполнения влияют пять факторов; размер массива М, число проходов (т. е. число различных смещений) Т = С, сумма значений смещений в последовательности В = Ье + ' ' + Ь» — 1., число сравнений В + ФТ вЂ” 5 — А и число перезаписей В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
