AOP_Tom3 (1021738), страница 47
Текст из файла (страница 47)
2 показано, как выбранная нами для примеров последовательность полностью сортируется при помощи этого метода за 11 итераций. В скобки заключены подмассивы, которые еще предстоит рассортировать; в программе эти подмассивы можно представлять двумя переменными двоичными [1, г) [граяицы рассматриваемого в данный момент массива) и стеком дополнительных пар [1ю юь), Каждый раз, когда массив разбивается, помещаем в стек больший из подмассивов и начинаем обрабатывать оставшийся; и так до тех пор, пока не будут получены тривиально короткие массивы. Как показано в упр. 20, такая процедура гарантирует, что в стеке никогда не будет находиться более 1я Х элементов. Только что описанную процедуру сортировки можно назвать обменной соршировкой с разделением. Ее идея принадлежит Ч. Э.
Р. Хоару, интереснейшая статья которого [С. А. Н. Ноаге, Сошр. Х б [1962), 10 — 15[ — одно из наиболее исчерпывающих из когда-либо опубликованных сообщений об этом методе. Хоар окрестил свой метод "цшсЫогг" [ "быстрая сортировка" ), и зто название вполне соответствует действительности, так как внутренний цикл вычислений при реализации на любом из современных компьютеров оказывается очень быстрым. При всех сравнениях, выполняемых на текущей итерации, используется один и тот же ключ, так что соответствующее значение можно держать в регистре. Обмен тактами между сравнениями выполняется только в отношении единственного индекса.
Более того, количество перезаписей данных довольно малб — обработка табл. 2, например, требует всего лишь 17 операций перезаписи данных. Вспомогательные операции [требуемые для управления стеком и переменными 1, у) не сложны, но все же из-за них процедура быстрой сортировки посредством разделений пригодна, в основном, при больших значениях А'. Поэтому в следующем алгоритме используется несколько измененная стратегия обработки коротких подмассивов. Таблица 2 БЪ|СТРАЯ СОРТИРОВКА (1, г) Стек (8,16) (8,16) (8,16) (8,16) Алгоритм ь| (Бис?прая сор?цороева). Записи В|,...',А|е перекомпоиовываются в пределах того же пространства памяти. По завершении сортировки их ключи будут упорядочены: К! « Кк?. Нужен вспомогательный стек для хранения не более чем (!8 Х[ элементов. Этот алгоритм (рис.
19) соответствует описанной выше процедуре быстрой сортировки посредством разделений с небольшими изменениями с целью новь!щения эффективности. а) Предполагается наличие искусственных ключей Ко = — со и Кв.е! — — +оо, таких, что для 1 < ! < А?. КО < К < КА'е! (Равенство допускается.) Ь) Подмассивы, состоящие из М и менее элементов, являются нерассортированными слева до самого конца выполнения процедуры. Затем выполняется единственный проход сортировки методом простых вставок, где М > 1 — параметр, который. выбирается, как описано ниже. (Эта идея принадлежит Р. Седгевику и позволяет сэкономить на вспомогательных операциях, которые необходимы, если непосредственно использовать метод прямых вставок по отношению к коротким подмассивам.) с) Записи с одинаковыми ключами меняются местами, хотя это не является строго необходимым.
(Эта идея, принадлежащая Р. К. Синглтону (Н. С. 8|п81е?оп), способствует разделению подмассивов почти пополам, если имеются равные ключи; см. упр. 18.) ь|1. [Начальная установка.] Если Х < М, перейти к шагу (49. В противном случае очистить стек и установить ( < — 1, г 4- )1?. ь|2. [Начать новую итерацию.) (Необходимо рассортировать подмассив В!... Л„. Нз самого существа алгоритма вытекает, что т > 1+ М и К! ! < Л| < К„„! при ( < 1 < г.) Установить !' е- |, 1 4 — г + 1 и к 4 — к!. (Обсуждение наилучшего выбора К приведено ниже.) [503 087 [275 087 [170 087 [061 087 061 [08? 061 087 061 087 061 087 061 087 061 087 ОШ 087 061 087 512 061 908 154 061 426 154 ООЦ 275 1541 170 275 1541 170 275 154 170 275 154 170 275 154 170 275 154 170 2Т5 154 170 275 154 170 275 154 170 275 170 897 275 653 1701 503 (897 653 426 503 (897 653 426 503 [897 653 426 503 (897 653 426 503 [897 653 426 503 1765 653 426 503 [677 653 426 503 [509 653 426 503 509 [653 426 503 509 [512 426 503 509 512 426 154 509 908 512 509 908 512 509 908 512 509 908 512 509 908 512 509 703 512 509 703 512 509 612 5121 677 ш2 5121 677 6121 653 677 612 653 677 612 677 765 612 677 765 612 677 765 Ш 2 677 765 612 677 765 612 677 765 612 6?7) 897 б!21 765 897 703 765 897 703 765 897 ТОЗ 765 897 703 765 897 7031 (1,16) 7031 (1,6) 703( (1,4) 703) (1,3) 703) (2,3) 7031 (8,!6) 908 (8,14) 908 (8,!3) 908 (8,11) 908 (9,11) 908 (9,!О) Рис.
19. Обменная сортировка с разделением (быстрая сортировка). ЦЗ. [Сравнить К;:К.] (В этот момент массив перекомпонован таким образом, что Кь < К для 1 — 1 < й < 1 К < Кь для 1 < )с < г+ 1 (14) и 1 < 1 < 1'.) Увеличить 1 на 1; затем, если К; < К, повторить этот шаг.
(Как только К. > К, итерацию нужно прекратить, сохранив 1 < 1.) Я4. [Сравнить К: К .] Уменьшить з' на 1; затем, если К < Ку, повторить этот шаг. (Как только К > К; м итерацию нужно прекратить, сохранив 1 > 1 — 1.) ь45. [Провериты:1.] (В этот момент соблюдается условие (14), кроме гчучэя, когда lс = 1 и к = 13 также К; > К > К, и г > 1 > 1 — 1 > 1.) Если у < з, переслать Л~ +э Л; и перейти к шагу Ц7.
(46. [Взаимный обмен.] Выполнить взаимный обмен Л; еэ Л, и вернуться к шагу ЯЗ. 147. [Поместить в стек.] (Теперь подмассив Л~... Л ... Л, разделен так, что Кь < К, при 1 — 1 < 1 < у и К < Кь при у' < Й < г + 1.) Если г — у >,у — 1 > 34, то поместить в стек (у+1,г), установить г ь- 1 — 1 и перейти к шагу (42, Если у — 1 > г — 1' > М, то поместить в стек (1,з — 1), установить 1 +- 1'ч-1 и перейти к шагу Я2.
(Каждый элемент в стеке — пара (а, Ь) -- это запрос на сортировку подмассива Л,...Лм которую нужно будет выполнить позже.) В противном случае, если г — 1 > М > 1 — 1, установить 1 +- ~ + 1 и перейти к шагу Я2 или, если 1 — 1 > М > г — у, установить г < — у — 1 и перейтн к шагу (42. с48.[Извлечь из стека.] Если стек не пуст, извлечь верхний элемент стека (Г,г'), установить 1 < — Г, г < — г' и возвратиться к шагу Я2.
449.[Сортировка методом простых вставок.] Для 1 = 2, 3, ..., М, если Ку ~ > К., выполнять следующие операции: установить сначала К +- Кз Л +- Л,, 1 <— у — 1, а затем — Льы +- Л, и 1 ь- 1 — 1 один или более раз до тех пор, пока не выполнится условие К; < К. Далее установить Лг ы < — Л. (Это, по существу, алгоритм 5.2.18, модифицированный в соответствии с идеей упр. 5.2.1 — 10 и ответом к упр.
5.2.1-33. Шаг Я9 можно опустить, если М = 1. Предупреждение. Последняя стадия — сортировка методом простых вставок — может скрыть ошибки нз шагах Я1-Я8, поэтому учтите, что программу, реализующую этот алгоритм, следует тщательно проверить, не особо доверяя тому факту, что получен правильный результат!) Соответствующая М1Х-программа довольно велика, но не сложна. На самом деле большая часть команд относится к шагу ()7, на котором проводятся совершенно очевидные манипуляции переменными.
В, ь+ Вз. ~з. с к.: к. Повторить„если К < К, сс, сьвкш ~р, й < — Вм В1 ь- В. с)7. Поместить в стек г14 <- г — 1 — М. Программа 14 (Обменная соршироека с разделением). Записи, которые предстоит рассортировать, находятся в ячейках от 1ИРОТ+1 до 1ИРОТ+И. Предполагается, что в ячейках 1ИРОТ и 1МРОТ+И+1 содержатся значения, соответственно минимальное и максимальное для разрядной сетки компьютера М1Х. Стек располагается в ячейках БТАСК+1, БТАСК+2, ...; точное число ячеек, которые необходимо отвести под стек, обсуждается в упр.
20. Значения регистров: г12 к— в 1, г13:— г, г14 = 1, г15 = .1, г16 к— в размер стека, гА =— К с— е Н. Полагаем, что Аг > М. А ЕЦО 2:3 Первый компонент элемента стека. В ЕЦО 4:Б Второй компонент элемента стека. 01 БТАВТ ЕИТ6 0 1 Я1. Начальная становка. Очистить стек. 00 ЕИТ2 1 1 1ь-1.
ОЯ ЕИТЗ И 1 г < — Ас. 04 2Н ЕИТ5 1,3 А О2. Начать иов ю иге а ию. 1' ь- г+ 1. 05 1ОА 1МРОТ,2 А К+- Кь 00 ЕМТ4 1,2 А 1ь-1+1. 07 ЛМР ОР А Перейти к шагу ()3, опустив Б +- 1 + 1", 00 БН 10Х 1МРОТ,4 В ()6. Взаимный обмен. 09 ЕИТ1 1ИРОТ,4 В 10 МОЧЕ 1ИРОТ,Б В 11 БТХ 1ИРОТ,Б В 1Я ЗН 1ИС4 1 С' — А 1Я ОН СИРА 1МРОТ,4 С' Ц 30 ЗВ С Повторить, если К > К;. 15 4Н ЮЕС5 1 с-с' С~~.
с к:к 10 СИРА 1ИРОТ,5 С вЂ” С' 17 31 4В С вЂ” С' 1Я 5Н ЕМТХ 0,5 В+.4 19 ОЕСХ 0,4 В+А 00 ЛХР БВ В + А Перейти к 1аагу (чб, если 1' > 1. 01 ЕОХ 1МРОТ,Б А ЯЯ ЯТХ 1ИР!71,2 А ЯЭ БТА 1ИРОТ,Б А 04 7Н ЕИТ4 0,3 А 05 РЕС4 М,5 А Яб ЕИТ1 0,5 А 37 ОЕС1 М,2 А гП < — 1' — 1 — М. ЭЯ ЕМТА 0,4 А 00 РЕСА 0,1 А ЯО ЯАМИ 1Р А Переход, если г — 1' > 1 — 1.
Я1 31МР ВР А' Перейти к шагу С)8, если М > 1 — 1 > т — 1 ЯЯ 34ИР ЗР Я' + Ас Переход, если 1 — 1 > М > г — 1'. ЯЯ 1МСБ 1 У (Сейчас 1 — 1 > г — 1 > М.) Я4 БТ2 БТАСК,б(А) Я' 5' 5! 5'+ Ав' 5'+ А'в А — А' ЕИТА -1,5 ЯТА ЯТАСК,6(В) ЕМТ2 1,5 ЛМР 2В 54ИР 8Р 85 Юб 87 4Н 88 99 1Н (у+1, т) ~ стек. т +- !' — 1.
Перейти к шагу Я2. Яб. Извлечение вз стека. Н,+, е- Н,. 1 е-1 — 1. Повторить, если К < К,. Ньы +- Н. 2 < ! < !7. Анализ метода быстрой сортировки. Информацию о времени выполнения, при- веденную вместе с программой (4, нетрудно вывести из закона сохранения Кирхгофа (см, раздел 1.3.3) и из того факта, что все помещенное в стек, в конце концов, оттуда извлекается. Закон Кирхгофа в применении к шагу (42 показывает, что А = 1 + (5' + Ав') + (5 — 5' + Ав) + 5 = 25 + 1 + Ав + А'".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
