AOP_Tom3 (1021738), страница 39
Текст из файла (страница 39)
При 1 = 1 этот алгоритм сводится к алгоритму Б. Ш. [Цикл по а) Выполнить шаг 132 при э = 1 — 1, » — 2,..., О, после чего завершить процедуру. 132. [Цикл по 71] Присвоить 1»» — Л, и выполнить шаги от 03 до Вб при 7» < 7 <»У. [Для сортировки элементов, отстоящих один от другого на»» позиций, воспользуемся методом простых вставок и в результате получим К, < К»».ь для 1 <» <»У — 7». Шаги от 03 до 136, по существу, такие же, как соответственно от 82 до 85 в алгоритме Я.) РЗ.
[Установка», К, Л.) Присвоить»» — 7 — »», К» — К, Л»- Л.. Р4. [Сравнение К: К».,' Если К > Ко то перейти к шагу Вб. Таблица 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; 154 087 426 061 509 170 677 503 653 512 275 908 612 897 765 703 Сортировка через 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 > О, то возвратиться к шагу 04.
Пб. [ПеРемещение Л на место Лььь,) ПРисвоить Лб ьь +- Л. $ Соответствующая программа для Н1Х не намного длиннее, чем наша программа для метода простых вставок. Строки 08 — 19 этой программы перенесены из программы Я в более общий контекст алгоритма П. Программа П [Сор«воровка Шелла). Предполагается, что смещения для сорти- ровки хранятся во вспомогательной таблице и Ь, находится по адресу Н+ в; все смещения сортировки меньше Аг.
Содержимое регистров таково: гП г— в 1 — Аг; г12 г— я 1; гА: — Л ив з К; г13 = в; г14 = Ь. Обратите внимание на то, что зта программа сама себя изменяет. Это сделано для того, чтобы добиться более эффективного выполнения внутреннего цикла. 01 ЯТАНТ ЕМТЗ Т-1 Ьб. Ц вбб, * — 1. 08 1Н 1.04 Н, 3 Рг. Ябб, б ов ЕМТ1 1МРОТ,4 Модификация адресов в трех 04 ЯТ1 ЯР(О:2) командах основного цикла.
05 ЯТ1 бр(0:2) 06 ЕММ1 -М,4 г11 +- 1«' — Ь. 07 ЯТ1 ЗР(0:2) ОВ ЕМТ1 1-М,4 Оо 2Н ЬОА 1МРОТ+М,1 10 ЗН ЕМТ2 М"Н,1 11 4Н СИРА 1МРОТ,2 19 10Е 6Р 13 10Х 1МРОТ,2 14 ЯН ЯТХ 1МРОТ+Н,2 15 ОЕС2 0,4 16 12Р 4В 17 6Н ЯТА 1МРОТ+Н,2 1В 7Н ХМС1 1 19 11МР 2В 90 ОЕСЗ 1 91 1ЗММ 1В ЖТ вЂ” Я 1т'Т вЂ” Я Т Т г>в>0. 4 1 Т Т Т Т Т Т Т 57Т вЂ” Я А«Т — Я В+1«)Т вЂ” Б — А В+ЖТ вЂ 5 в В В В В 5)Т вЂ” Я 1+- 5+1.
ПЗ. П исвоить б К Л. б «-1 — Ь. [Изменяемая команда) вб. гб кк. Перейти к шагу Пбб если К > К,. 1)5 Пе вписать меиьшять А В«ьл «- В [Изменяемая команда) 1«- б — Ь. Перейти к шагу П4б если «> О. ьб. вбь~~ь [и ! ьвбьб в 1 «-1+ 1.
Перейти к шагу ПЗ, если 1' < 07. ьАнализ метода Шелла. Для рационального выбора последовательности значений смещений сортировки Ь| ы..., Ье для алгоритма П нужно проанализировать время выполнения как функцию от зтих смещений. Такой анализ приводит к постановке очень красивьгх, но еще не до конца решенных математических задач; никому до сих пор не удалось найти наилучшую возможную последовательность смещений для больших Ж. Тем не менее известно довольно много интересных свойств сортировки методом Шелла с убывающим смещением, и мы здесь их кратко изложим; подробности будут рассмотрены в приведенных ниже упражнениях. [Читателям, не склонным к пространным математическим выкладкам, лучше пропустить следующие несколько страниц вплоть до начала обсуждения метода вставки в список, который следует за формулой (12).,' Счетчики частот выполнения в программе П показывают, что на время выполнения влияют пять факторов: размер массива Х, число проходов (т.
е. число различных смещений) Т = г, сумма значений смещений в последовательности о=йо+ +~И вЂ” 1 число сравнений В + ЖТ вЂ”  — А и число перезаписей В. Как и при анализе программы Б, здесь А равна числу левосторонних минимумов, встречающихся при промежуточных операциях сортировки, а В равно числу инверсий в подмассивах. Основным фактором, от которого зависит время выполнения, является величина В, позтому на нее мы в основном и обратим свое внимание. При анализе будет предполагаться, что ключи различны и первоначально расположены в случайном порядке.
Назовем операцию шага 02 Ь-сортировкой. Тогда сортировка методом Шелла состоит из 1ц ысортировки, эа которой следует Ьс т-сортировка, ..., за которой следует Ьр-сортировка. Массив, в котором К, < К,+ь при 1 < т' < Х вЂ” Ь, будем называть Ь-упорядоченным. Рассмотрим сначала простейшее обобщение простых вставок, когда имеется всего два смещения: Ь1 — — 2 и Ье —— 1.
Во время второго просмотра имеем 2-упорядоченную последовательность ключей К~ Кю .. Ки. Легко видеть, что число перестановок а1 ат... в„множества 11, 2,..., и), таких, что а; < аы х при 1 < 1 < и — 2, равно 1п/2! так квк существует всего одна 2-упорядоченная перестановка для каждого выбора 1п/2) злементов, расположенных в четных позициях ат а4...; тогда остальные ~п/21 элементов попадают в позиции с нечетными номерами. После 2-сортировки случайного массива с одинаковой вероятностью может получиться любая 2-упорядоченная перестановка. Каково среднее число инверсий во всех таких перестановках? Пусть А„— суммарное число инверсий во всех 2-упорядоченных перестановках множества 11, 2,..., и). Ясно, что А1 = О, Ат = 1, Аз = 2; рассмотрев шесть случаев 1324 1234 1243 2134 2143 3142, находим, что А4 = 1 + 0+ 1+ 1 + 2 + 3 = 8.
Чтобы проанализировать А„в общем случае, рассмотрим "решетчатую диаграмму" на рис. 11 для и = 15. На такой диаграмме 2-упорядоченную перестановку множества (1,2,...,и) можно представить в виде пути из верхней левой угловой точки (0,0) в нижнюю правую угловую 00 10 20 40 00 70 00 Рис. 11. Соответствие между 2-упорядочением и путями иа решетке. Курсивом набраны веса, соответствующие числу инверсий в 2-упорядоченной перестановке. точку ((и/2), (и/2)), если выполнить очередной Ь-й шаг пути вправо или вниз в соответствии с тем, где находится й: в четной или нечетной позиции перестановки. Этим правилом определяется взаимно однозначное соответствие между 2- упорядоченными перестановками и и-шаговыми путями из одного угла решетчатой диаграммы в другой.
Например, изображенный на рис. 11 путь соответствует перестановке 2 1 3 4 6 5 7 10 8 11 9 12 14 13 15. Далее, вертикальным отрезкам пути можно приписать веса, как показано на диаграмме; отрезку, ведущему из точки (1, 1) в точку (1+1, у), приписывается вес ~4 — у ~. После несложных умозаключений читатель сможет убедиться в том, что сумма этих весов вдоль каждого пути равна числу инверсий в соответствующей перестановке; зта сумма также равна количеству заштрихованных квадратиков между данным путем и другим ступенчатым путем, выделенным на рисунке пунктирной линией с жирными точками (см. упр.
12). Так, например, перестановка (1) содержит 1+ 0+ 1+0+1+2+1+0=бинверсий. Если а < и' и Ь < Ь', то число допустимых путей из (а, Ь) в (а', Ь') равно числу способов объединения а' — а вертикальных отрезков с Ь' — Ь горизонтальными, а именно а' — а+ Ь' — Ь Следовательно, число перестановок, соответствующие пути которых проходят через вертикальный отрезок нз (4, 1) в (1+1, у), равно ( )Гмс- ) Умножая это значение на вес данного отрезка и суммируя по всем отрезкам, полу- Ат„—— (2) Аи ч.1 = о<учи Знаки абсолютной величины в этих суммах несколько усложняют вычисления, но в упр.
14 показано. что выражение для в~личины А„имеет на удивление простой вид: (и/2)2" "-. Следовательно, .среднее число инверсий в случайной 2-упорядоченной перестановке равно (и/2)2н-2 По формуле Стирлинга эта величина асимптотически приближается к ~/к/128 па~э еэ 0.15пэ~т.
Как легко видеть, максимальное число инверсий равно (~/2) + 1) 1 2 / 8 Полезно более тщательно проанализировать распределение числа инверсий, рассмотрев производящие функции о1(г) = 1, 62(е) — 1 + э~ 6з(а) = 1 + 2г, 6э(г) = 1 + За + г + а~, как в упр. 15. Таким образом найдем, что стандартное отклонение тоже пропорционально пэ~', так что число инверсий не слишко;1 устойчиво распределено около среднего значения.
Рассмотрим теперь общий случай алгоритма 0 с двумя проходами, когда смещения сортировки равны 6 и 1. Теорема Н. Среднее число инверсий в 6-упорядоченной перестановке множества (1,2,...,п) равно где д = (и/6) н г = и шой 6. Эта теорема принадлежит Дугласу Х. Ханту (Воп81ав Н. Нппс), [ВасЬе1ог'в 16ез1в, РНпсетоп Сшчегв1су (Арг!1, 1967)). Заметим, что формула справедлива и при 6 > и и дает верный результат: /(и, 6) = — (."). Доказательство.
В 6-упорядоченной перестановке содержится г упорядоченных полпоследовательностей длиной д + 1 и 6 — г подпоследовательностей длиной о. Каждая инверсия образуется из элементов двух различных подпоследовательно- стей. а каждая пара различных упорядоченных подпоследовательностей в случайной 6-упорядоченной перестановке определяет случайную 2-упорядоченную перестановку. Поэтому среднее число инверсий равно сумме средних значений числа инверсий во всех парах различных подпоследовательностей, а именно (2) (2~ -2) ~ (Ь 1) ( 1 ) (2ю) Следствие. Если последовательность смещений 6, ы ...,6ы 6в удовлетворяет условию 6„.г1 шестой, = О при à — 1 > в > О, (5) то средне~ число операций перезаписи в алгоритме О равно (б) (г,/(о„+1, 6, 1/6,) + (6к — г,)/(в„6,, 1/6,)), С>в>О где г, = Ф тод 6„, о, = (Ж/6,), 6~ = %6с ы а функция / определяется форму- лой (4).
Докавашельсшво, Процесс 6;сортировки предусматривает сортировку методом простых вставок г, (6кч.1/6,)-упорядоченных подмассивов длиной о„+1 и (6, — г,) таких подмассивов длиной о,. Поскольку предполагается, что исходная перестановка случайна и все ее элементы различны, то из условий делимости следует, что каждый из подмассивов — "случайная' (6к ы/6,)-упорядоченная перестановка в том смысле, что все (6ь ы/6,)-упорядоченные перестановки равновероятны. 3 Условие (5) этого следствия всегда выполняется для двух'проходной сортировки методом Шелла, когда смещения равны соответственно 6 и 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
