AOP_Tom3 (1021738), страница 42
Текст из файла (страница 42)
8 показано несколько первых шагов сортировки шестнадцати чисел, выбранных нами для примеров. Таблица 8 ПРИМЕР РЕАЛИЗА1[ИИ МЕТОДА ВСТАВКИ В СПИСОК У: 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 К~". — 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703 Ь,". 16 0 Ь7: 16 0 15 Ь, 14 — — — — — — — — — — 16 0 15 Программа Ь (Мерпод вставки в список). Предполагается, что ключ Кр хранится по адресу 1йРОТ+7'(О:3), а Ь хранится по адресу 1ВРОТ+7'(4:5). Значения в регистрах таковы: гП = 7'; г12 г— н р; г13 = 9; гА(О: 3)— : К. 01 КЕУ ЕОО 0: 3 09 Ь1ВК ЕОО 4: б Ж>1>1.
э 00 БТАНТ 04 00 00 07 2Н 00 00 ЬО ЗН 11 12 4Н 10 14 10 ВН 16 17 ОН 18 ЕИТ1 И БТ1 1ИРОТ(1.1ИК) БТЕ 1ИРОТ+И(Ь1ИК) ЗИР бр 1.02 1ИРОТ(ЬТИК) ЕИТЗ 0 ЬВА 1ИРОТ,1 СИРА 1МРОТ,2(КЕУ) 1ЬЕ ВР ЕМТЗ 0,2 ЬР2 1ИРОТ,З(Ь1ИК) 12Р ЗВ БТ1 1ИРОТ,З(Ь1ИК) БТ2 1ИРОТ,1(1.1ИК) ОЕС1 1 11Р 2В 1 1 1 1 г"гг — 1 г'гг — 1 г"гг — 1 В+У вЂ” 1 — А В+Я вЂ” 1 — А В В В Ат — 1 Ж вЂ” 1 дг )уг Я.
Ь, ~- )г. Ьгг р — О. Переход на уменьшение 1. Х 2. Ъсгаиовка й 4К. р р- Ьв. д < — О. Кр-К,. 13. С авнить К: К . Перейти к шагу 1.5, если К < Кр. р Рр 1р. Перейти к шагу ЬЗ, есаи р > О. Ьо. Вставить в список. Ьр ь- 1 Ь, ь-р. Время выполнения этой программы равно 7В+ 14% — ЗА — б машинных циклов, где Ю вЂ” длина массива, А + 1 — - число правосторонннх максимумов, а В— число инверсий в исходной перестановке. (Ср. с анализом программы Б. Обратите внимание, что программа Ь не перемещает запнси в памяти; зто можно сделать, как в упр.
5,2 — 12, затратив дополнительно 20ггг машинных циклов.) Програима Б требует (9В+ 10?гг — 3.4 — 9) и, а так как В равно примерно г ЮР, то нетрудно видеть, что за счет дополнительного пространства памяти, выделенного для полей связи, удалось сэкономигь примерно 22% времени выполнения. Тщательно продумав программу, можно сберечь еще 22% (см. упр.
33), гго время выполнения все же останется пропорциональныи Х . Лодведегг итог сделанному. Мы начали с алгоритма Б -- простого и очевидного алгоритма сортировки, который выполняет около р грг сравнений и около ргу~ перемещений записей данных в памяти. Этот алгоритм был усовершенствован путем использования бинарных вставок, прн которых выполняется около йр 1К гг7 сравнений и г Ггге перемещений записей данных в памяти. Несколько изменив структуру данных, применив двухпутевые вставки, нам удалось сократить число перезаписей до — 'Хз.
При сортировке методом Шелла с убывающим смещением число сравнений и перезаписей снижается примерно до?р'Р?в для тех значений 117, которые встречаются на практике; при ю — г оо зто число можно сократить до порядка ггг(1окггг)~. Дальнейшее стремление улучшить алгоритм Б с помощью связной структуры данных привело нас к методу вставки в список„который требует около — 'Ж~ сравнений, О перезаписей и 2ар операций изменения связи. Можно ли объединить лучшие свойства этих методов, т.
е. сократить число сравнений до порядка ггг 1об?1г, как при бинарных вставках, н в то же время исключить перемещения записей в памяти, как при вставках в список? Ответ утвердительный — нужно перейти к древовидной структуре данных. Такой вариант впервые был исследован в 1957 году Д. Дж. Уилером (П. Л. 1гг(гее1ег), который предложил использовать двухпутевые вставки до тех пор, пока не возникнет необходимость перемещать записи в памяти.
Вместо операции перезаписи он предложил вставлять указатель на новую область памяти и рекурсивно применять ту же процедуру ко всем элементам, которые должны вставляться в эту новую область памяти. Ориги- " -' "Т"'-'— 154 !70 275 42б 509 б12 055~ Я97 Б77 705 703 Рнс.
13. Пример схемы Унлера для вставок в дерево. нальный метод Уилера (см. А. 8. 11он81аб, Сошр. Х 2 (1959), 5] предполагал использование довольно замысловатой комбинации последовательной и связной памяти с узлами переменного размера; для тех шестнадцати чисел, которые используются в качестве примера неупорядоченной последовательности, таким способом было бы сформировано дерево, показанное па рис. 13. Аналогичную, но более простую схему со вставками в бинарную древовидную структуру изобрел К. М. Бернерс-Ли (С. М.
Вегпегб-1.ее) примерно в 1958 году (см. Сошр. 3. 3 (1960), 174, 184). Поскольку сам метод с использованием бинарного дерева и его модификации очень важны как для сортировки, так и для поиска, его подробное обсуждение мы отложим до раздела 6.2.2 главы 6. Еп1е один путь улучшения метода простых вставок — попытаться вставлять несколько записей одновременно. Если, например, имеется массив из 1000 элементов и 998 из них уже рассортированы, то алгоритм 8 выполнит еше двв просмотра массива (вставив сначала Вэээ, а потом 77!ббб).
Очевидно, можно сэкономить вРемм, если сначала сравнить ключи К999 и К!000 н выяснить, какой из них больше„а затем вставить оба ключа за один просмотр массива. Комбинированная операция такого рода требует около 2А7 сравнений и перезаписей (см. упр. 3.4.2 — 5) вместо двух просмотров, примерно по -,' Х сравнений и перезаписей каждый. Иначе говоря, обычно полезно "группировать" операции, которые требуют длительного поиска, чтобы можно бьыо выполнить несколько операций сразу.
Если довести эту идею до ее естественного завершения, то будет заново открыта сортировка посредством слияния, настолько важная, что ей посвящен отдельный раздел (5.2.4). Сортировка с вычислением адреса. Ну уж теперь-то, несомненно, исчерпаны все возможные способы усовершенствования методов простых вставок! Но давайте подумаем еще. Представьте себе, что вам поручили расставить несколько дюжин книг на полке по фамилиям авторов, причем книги берутся с по.л в случайном порядке.
Ставя книгу на полку, вы, естественно, попробуете прикинуть, где примерно она будет, в конце концов, стоять, я таким образом потенциально сократите число необходимых в будущем сравнений н перестановок. Эффективность процесса повысится, если на полке будет немного больше места, чем это абсолютно необходимо. Такой метод для реализации компьютерной сортировки впервые предложили Исаак (1баас) и Синглтон (Япй!есоп) (см. з 4СМ 3 (1956), 169-174); он получил дальнейшее развитие в работе Тартера (Тагбег) и Кронмзла (Кгопша1) [см. Ргос. АСМ Хас'1 Сопб 21 (1966), 331 †3), Пришли Пришли Пришли Всего 4 элемента 8 элементов 12 элементов 061, 087, 170 061, 087, 154, 170 061, 087, 154, 170 275 275, 426 275,426 503,512 503,509,512,653 503,509,512,612,653,677,703 897, 908 897, 908 765, 897, 908 Список 1: 061, 087 Список 2: Список 3.
503,512 Список 4: (Программа М, описанная ниже, в действительности вставляет ключи в обратном порядке, К1е, ..., Кы Кы но окончательный результат тот же.) Благодаря организации в памяти структуры связных списков не возникает проблем, связанных с выделением памяти прн изменении длины списка. При желании в конце выполнения программы все списки можно объединить в один (см.
упр. 35). Программа М (Вставка в несколько списков). При разработке этой программы сделано такое же предположение, как и в программе Ь, но ключи должны быть неотрицательными, т. е. 0 < К < (НттЕ812Е)э. В программе этот диапазон делится на И равных частей посредством умножения каждого ключа на соответствуюшую константу. Головные элементы списков хра- нятся в ячейках от НЕА0+1 до НЕА0+И. Сортировка с вычислением адреса обычно требует дополнительного пространства в памяти либо для того, чтобы оставить достаточно свободного места и не делать много лишних перемещений, либо для хранения вспомогательных таблиц, которые позволяли бы учитывать неравномерность распределения ключей. (См.
сортировку методом подсчета распределения (алгоритм 5.2Р), которая является разновидностью сортировки с вычислением адреса,) Дополнительное пространство будет, по-видимому, использоваться наилучшим образом, если отвести его для полей связи, как в методе вставок в список, К тому же отпадает необходимость в выделении отдельных облагтей для ввода и вывода; все операции можно выполнить в одной н той же области памяти. Основная цель — так обобщить метод вставок в список, чтобы работать не с одним списком, а с несколькими.
Каждый список содержит ключи из определенного диапазона. Мы делаем важное предположение о том, что ключи распределены довольно равномерно и не скапливаются хаотически в отдельных областях значений. Множество всех возможных значений. ключей разбивается на М частей, и предполагается, что данный ключ попадает в данное подмножество с вероятностью 1/М. Отводим дополнительную память для головных элементов М списков, а каждый список обрабатываем, как при простых вставках в список. Нет необходимости приводить здесь этот алгоритм со всеми подробностями. Достаточно вначале установить все головные элементы списков равными Л, для каждого вновь поступившего элемента предварительно решить, в какое из М подмножеств он попадает, после чего вставить его в соответствующий список, как в алгоритме Ь. Чтобы проиллюстрировать этот метод в действии, предположим, что наши 16 ключей разделены на М = 4 поддиапазона: 0-249, 250 — 499, 500-749, 750 — 999.
В процессе сортировки по мере того, как будут вставляться ключи Кы Кэ, ..., К,е, получатся следующие конфигурации. (14) Поэтому средние значения величин А и В в общем случае равны А,„,=М~ (' )( — ) (1 — — ) Н„; (15) 01 КЕЧ ЕЦО 1: 3 02 ЬТМК ЕЦБ 4:Я 0Ю ЯТАНТ ЕМТ2 Н 1 04 ЯТЕ НЕАО,2 М НКАП(р) < — Л. 00 ВЕС2 1 М Об 12Р «-2 М 07 ЕИТ1 И 1 00 2Н ЬРА ТМРОТ,1(КЕЧ) )Ч 00 НОЬ =Н(1:3) )Ч гА «- '1ЛХ К,/ВЧТЕБ12Е~1'. 10 ЯТА «+1(1:2) )Ч 11 ЕИТ4 О )Ч г14 «- гА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
