Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 32
Текст из файла (страница 32)
Более того, количество перезаписей данных довольно малб — обработка табл. 2, например, требует всего лишь 17 операций перезаписи данных. Вспомогательные операции (требуемые для управления стеком и переменными 1, 3) не сложны, но все же из-за них процедура быстрой сортировки посредством разделений пригодна, в основном, при болыпих значениях Ю. Поэтому и следующем алгоритме используется несколько измененная стратегия обработки коротких подмассивов. Таблица 2 БЫСТРАЯ СОРТИРОВКА (1, т) Стек Алгоритм (4 (Вмсшрал со)нппроока). Записи Л1,...', Нот перекомпоновываются в пределах того же пространства памяти.
По завершении сортировки их ключи будут упорядочены: К1 « ° ° ° Кю Нужен вспомогательный стек для хранения не более чем ]!8Ю] элементов. Этот алгоритм (рис. 19) соответствует описанной выше процедуре быстрой сортировки посредством разделений с небольшими изменениями с целью повышения эффективности. а) Предполагается наличие искусственных ключей Ко = -оо н Км+1 = +ОО, такнх, что К.<К!<К„+, для 1 < ! < )т". (Равенство допускается.) Ь) Подмассивы, состоящие из М и менее элементов, являются иерассортированными слева до самого конца выполнения процедуры. Затем выполняется единственный проход сортировки методом простых вставок, где М > 1 — параметр, который.
выбирается, как описано ниже. (Эта идея принадлежит Р. Седгевнку и позволяет сэкономить на вспомогательных операциях, которые необходимы, если непосредственно использовать метод прямых вставок по отношению к коротким подмассивам,) с) Записи с одинаковыми ключами меняются местами, хотя это не является строго н!ктбходимым.
(Эта идея, принадлежащая Р. К. Синглтону (В,. С. Яш81е!оп), способствует разделению подмассивов почти пополам, если имеются равные ключи; см. упр. 18.) (~1. (Начальная установка.] Если Ф < М, перейти к шагу (49. В противном случае очистить стек и уствновнть 1+- 1, г 4- )!т.
к42. (Начать новую итерацию.] (Необходимо рассортировать подмассив Щ... В,. Нз самого существа алгоритма вытекает, что г > 1+ М и К! 1 < К; < К,+! при 1 < ! < 7.) Установить ! е- 1, т' 4- г + 1 н К 4- К1. (Обсуждение наилучшего выбора К приведено ниже.) 150$ обт 1275 087 1170 обт 1061 087 ОЫ 1087 аы оВт об! обт оы обт 061 087 061 087 Об! 087 оы 087 Ы2 061 908 170 897 275 653 154 061 426 1701 503 (89Т 653 И4 Об!) 275 426 503 (897 6$3 1541 1ТО 275 426 503 (897 653 1541 !70 275 426 503 1,89Т 653 154 170 275 426 503 (897 653 154 170 275 426 503 176$ 653 !54 !70 275 426 503 1677 653 154 170 275 426 503 1509 653 И4 170 275 426 503 509 1653 И4 !70 275 426 503 509 1512 154 170 275 426 $03 509 512 426 154 509 612 677 765 908 Ы2 609 612 677 765 908 512 509 612 677 765 908 Ы2 509 612 677 76$ 908 $12 509 612 677 765 908 512 509 612 бтт 765 703 Ы2 509 612 677) 897 703 Ы2 509 ЬИ) 765 897 612 5121 677 703 765 897 612 5121 6Т7 703 Т65 897 6121 653 677 703 765 897 612 6$3 677 703 765 897 7031 (1,16) 703) П,б) (В,ы) тоз] (1,4) (В,ы) 703) (1,3) (8,)6) тоз) (2,3) (Ь,ы) таз) (В,ы) 908 (8,14) 908 (8,13) 908 (8,11) 908 (а,ы) 908 (9,10) 908 Рнс.
19. Обменная сортировка с разделением (бмстраи сортировка). ЯЗ. [Сравнить К,: К.) (В этот момент массив перекомпонован таким образом, что К» < К для1 — 1< 1 <1 К<К» для,у </с< с+1 (14) и) < т < Х.) Увеличить 1 иа 1; затем, если К; < К, повторить этот шаг. (Как только К.
> К, итерацию нужно прекратить, сохранив 1 < Х.) Я4. [Сравнить К:КХ.[ Уменьшить Х на 1; затем, если К < КХ, повторить этот шаг. (Как только К > К; и итерацию нужно прекратить, сохранив Х > 1 — 1.) 145. [Проверить 1:Х.] (В этот момент соблюдается условие (14), кроме случая, когда Й = 1 и Й = Х; также К; > К > К„и г > Х > 1 — 1 > 1.) Если Х < 1, переслать В~ »+ В и перейти к шагу Я7. Яб.
[Взаимный обмен.[ Выполнить взаимный обмен В; »» В. и вернуться к шагу»13. ЯТ. [Поместить в стек.) (Теперь подмассив В~... В»... В, разделен так, что К» < К при 1 — 1 < Л < Х и КХ < К» при Х < А" < г + 1.) Если г — т' > Х вЂ” 1 > ЛХ, то поместить в стек Ц+1,т), установить г »- Х вЂ” 1 и перейти к шагу Ц2, Если Х вЂ” 1 > г — Х > ЛХ, то поместить в стек (1м(-1), установить 1»- Х + 1 и перейти к шагу Ч2.
(Каждый элемент в стеке — парь (а, Ь) — это запрос на сортировку подмассива В,...В», которую нужно будет выполнить позже,) В противном случае, если т — Х > М > Х вЂ” 1, установить 1»- Х + 1 и перейти к шагу Я2 или, если Х вЂ” 1 > ЛХ > г — Х, установить и +- Х вЂ” 1 и перейти к шагу»42. Яй. [Извлечь из стека,) Если стек не пуст, извлечь верхний элемент стека (Г,г'), установить 1+- 1', г»- г' и возвратиться к шагу Я2. 149, [Сортировка методом простых вставок.) Для Х м 2, 3, ..., Х, если КХ 1 > К., выполнять слелукицие операции: установить сначала К +- К., В»- В, 1 +- Х вЂ” 1, а затем — В»»1 +- В; и 1 +- 1 — 1 один или более раз до тех пор, пока не выполнится условие К; < К, Далее установить В»т1 +- В.
(Это, по существу, алгоритм 5.2.15, модифицированный в соответствии с идеей упр. 5.2.1-10 и ответом к упр. 5.2.1-33. Шаг Я9 можно опустить, если М = 1. Хуредрпреждеиис. Последняя стадия — сортировка методом простых вставок — может скрьпь ошибки нз шагах 141-ЯЗ, поэтому учтите, что программу, реалнзующую этот алгоритм, следует тщательно проверить, не особо доверяя тому факту, что полу*ген правильный результат,') $ Соответствующая ИХХ-программа довольно велика, но не сложна. На самом деле бблыиая часть команд относится к шагу Я7, на котором проводятся совершенно очевидные манипуляции переменными, В; с+ В„. ос о~~шл: к.
' '+ 1 Повторизел если К < К, 95.Ли с 1: /'. В~ с- Вз. Вз +- Н. Ог. Поместить в стел г14+- 1 — 8 — М. Программа ьг ~Обысииал соргинроека с разделением), Записи, которые предстоит рассортировать, находятся в ячейках от ХИРОТ+1 до 1МРОТ+М. Предполагается, что в ячейках 1ИРОТ и ХИРОТ+И+1 содержатся значения, соответственно минимальное н максимальное для разрядной сетки компьютера Н1Х. Стек располагается в ячейках БТАСК+1, ЗТАСК+2„...; точное число ячеек, которые необходимо отвести под стек, обсуждается в упр. 20. Значения регнст1юв: г12 ьз 1, г13 гн г, г14 ьз 1, г15 гн 1, г16 гв размер стека, гА = К гн Н.
Полагаем, что 1Ч > М. А ЕЦО 2:3 Первый компонент элемента стека. В ЕОО 4 б Второй компонент элемента стека. 01 БТАВТ ЕМТ6 0 1 Я1. Нач ьиаи тзновка. Очистить стек. 08 ЕМТ2 1 1 1+- 1. 08 ЕИТЗ И 1 г т-7Ч. 08 2Н ЕМТБ 1,3 А ь)8. Начать лов иге, 8 с- г+ 1. 08 ЬОА ХМРОТ, 2 А К+- Кь 08 ЕМТ4 1,2 А 1+-1+1. 07 ЛЧР ОР А Перейти к шагу ЯЗ, опустив "1 +- 1+ 1". 08 6Н ЫХ 1МРОТ,4 В ЯО. Взаимный обмен, 00 ЕИТ1 ТМРОТ,4 В 10 ХОЧЕ 1МРОТ,Б В 11 БТХ 1ИРОТ, б В 18 ЗН ТИС4 1 С' — А 18 ОН СИРА 1МРОТ,4 С' Ц 80 ЗВ С' Повторить, если К > Кь 15 4Н ОЕСБ 1 С-С" Щ.~.У ~~,~ р — 1.
Ы СИРА 1ИРОТ,Б С вЂ” С' 17 Л. 4В С вЂ” С' 18 бн ЕМТХ О,б В+А 10 ОЕСХ 0,4 В+А 80 ОХР 6В В+А Перейти к шагу Цб, если 8 > 1. 81 1ОХ 1МРОТ, б А 88 ЗТХ 1НРОТ,2 А 88 БТА 1МРОТ,Б А 88 7Н ЕМТ4 0,3 А 88 ВЕС4 Н,б А 88 ЕМТ1 О,б А 87 ОЕС1 М,2 А г11 <- 8 — 1 — М. 88 ЕМТА 0,4 А 80 ВЕСА 0,1 А 80 ЛАММ 1Р А Переход, если г — 8 > 8 — 1. 81 81МР ВР А' Перейти к шагу С)8, если М > 8 — 1 > г — 8 88 84НР ЗР 8 +А~ Переход, если у — 1> М > г — 8. 88 1ИС6 1 Я' (Сейчас 8 — 1 > и — 8 > М.) 88 БТ2 ЗТАСК,6(А) Я' У + Ак! у+ экю А — А' ЕИТА -1,5 ЗТА ЗТАСК,6(В) ЕИТ2 1,5 8МР 2В .ИМР 8Р 86 86 87 4Н 88 УУ 1Н (1+1, г) ~ стек. г +- У вЂ” 1. Перейти к шагу Ц2.
()8. звлечеви из ка. В;+1 ~- В,. 1+-1-1. Повторять, если К < К,. В,+г э- В. Анализ метод» быстрой сортировки. Информацию о времени вьпюлнения, при- веденную вместе с программой (1, нетрудно вывести из закона сохранения Кирхгофа (см. раздел 1.3.3) и из того факта, что все помещенное в стек, в конце концов, оттуда извлекается. Закон Кирхгофа в применении к шагу ()2 показывает, что А = 1 + (Е' + А"') + (Š— о' + А") + Е = 25 + 1 + А" + Аш.
Следовательно, суммарное время реализации алгоритма составляет 24А+ 11Е+ 4С+ ЗЮ+ ВЕ+ 7Х+ 9Я машинных тактов, где число итераций разбиения; число взаимных обменов на шаге (16; число сравнений, выполненных во время разбиения; число случаев, когда Ь) 1 > К) в ходе выполнения сортировки методом простых вставок (шаг ()9); количество инверсий, удаленных в процессе простых вставок; количество случаев, когда происходит запись в стек. (16) (О э1 88 18 й (6 ЗН 86 67 8Н 68 АУ 60 61 9Н 68 2Н 68 6( 66 ЗН 66 4Н 67 68 6У 60 61 5Н 68 6Н 68 01МР 4В ТИС6 1 ЗТЗ ЗТАСК,6(В) ЕМТА 1,5 ЗТА ЗТАСК,6(А) ЕИТЗ -1,5 ЛНР 2В 1.92 ЗТАСК,6(А) Ы)3 ЗТАСК,6(В) ЮЕС6 1 06ИМ 28 ЕИТ5 2-М 1РА ХИР(УТ+И,5 СИРА ТИРВТ+М-1,5 УСЕ 6Р ЕИТ4 М-1,5 ЫК ТИЙТ,4 ЗТХ 1МРОТ+1,4 ВЕС4 1 СИРА ТИР()Т,4 Л. 4В БТА ХИР))Т+1,4 1МС5 1 25МР 2В 3 — Я'+ А"" Я вЂ” Е 3 — 3' ЯФ 3 — У Я вЂ” З'+ А" У+ Ак 3+1 5+1 9+1 3+1 1 Ф вЂ” 1 Х вЂ” 1 Х вЂ” 1 11 Е Е Е Е Е ,Р Х вЂ” 1 Х вЂ” 1 ((,6-1) ~ стек.
1 э-,у + 1. Перейти к ~вагу ()2. Перейти к шагу ()8, если М > г — у > >у — А Переход, если г — У > М > У вЂ” 1. (Сейчас г — У > У вЂ” 1 > М.) (Ег) с:= стек. Перейти к шш у ()2, если стек ие пуст. ()У. Со ака м ом л тмк вставок. у +- 2. К ~- К,, В +- В,. (В этом цикле г15 ш 1 — Х.) Переход, если К > К, ь (+-У вЂ” 1. Проанализировав эти шесть параметров, можно сделать обоснованный выбор значения параметра М, которым определяется "граница" между сортировкой методом простых вставок н методом разделения. Сам по себе анализ также весьма поучителен, поскольку алгоритм довольно сложен. В процессе анализа будут использоваться важные методики, которые читатели, освоившие их, смогут в дальнейшем применять самостоятельно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
