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