Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 26
Текст из файла (страница 26)
729 128 64 250 125 2Ы 125 255 127 255 12Т 127 Ы2 256 500 501 Ы1 513 257 129 65 257 Г29 129 65 65 683 341 171 85 341 171 85 377 233 144 89 55 34 21 233 144 89 55 34 21 377 365 336 306 170 90 275 125 929 505 505 ние числа Ю содержит, длинные цепочки нулей. Лазарус и Фрэнк р,втлгпэ и Ггвпк, САСМ 3 (1960)с 20 — 22) предложили использовать, по существу, ту же последовательность, но добавляя 1 там, где это необходимо, чтобы сделать все смещения нечетными. Хиббард 1Н1ЬЬагд, САСМ б (1963), 206-213) предложил использовать смещения вида 24 — 1; Папериов и Стасевич предложили последовательность 2~ + 1. Среди других естественных последовательностей, использованных для получения 256 576 192 243 81 32 16 62 31 63 31 63 31 63 31 63 31 63 31 31 33 17 33 1Т ЗЗ 17 33 17 33 17 43 21 43 21 255 63 257 65 341 85 13 8 13 8 144 55 122 41 364 121 121 112 48 45 18 169 91 121 55 209 109 209 109 209 109 60 140 20 64 16 48 16 27 9 8 4 15 7 15 7 15 7 15 7 Рб Т 15 7 15 7 9 5 9 5 9 5 9 5 9 5 11 5 11 5 15 7 17 5 21 5 5 3 5 3 21 8 14 5 40 13 40 13 21 7 10 5 49 13 25 11 41 19 41 19 41 19 1 6 1Т1 65 6 1 158 4 1 262 4 1 362 4 1 419 3 1 378 21 493 3 1 516 3 1 558 3 1 559 3 1 436 3 1 299 3 1 190 3 1 114 3 1 561 3 1 440 3 1 304 3 1 197 3 1 122 3 1 511 3 1 490 3 1 373 3 1 375 3 1 410 21 Ы8 2 1 432 3 1 456 2 1 440 4 1 437 4 1 268 3 1 432 2 1 465 7 1 349 5 1 446 5 1 512 5 1 519 5 1 382 249750 41667 26361 21913 20459 20088 18533 16435 7655 7370 7200 7445 8170 9860 13615 6745 6995 7700 9300 12695 7365 7490 8620 8990 9345 7400 7610 8Т95 8085 8900 9790 7840 6755 8698 6Т88 7725 7Т90 8165 1 2 3 4 5 6 7 10 9 9 9 8 7 6 5 10 9 8 7 6 10 9 6 6 6 ГЗ 12 7 6 с Т 9 6 8 8 7 6 табл.
6, — последовательности (2» — ( — 1)»)/3 и (3» — 1)/2, числа Фнбоначчи и предложенная Инсерпи и Седгевиком последовательность (8) для р = 2.5 и р = 2. также включены последовательности (Зг11») и (7»13»), аналогичные предложенной Праттом, поскольку они сохраняют асимптотический характер сходимости к О(Х(!ойдо) ), но приводят к более низким накладным расходам при малых )У.
Последний вариант в табл. 6 исходит нз другой последовательности, предложенной все тем же Седгевиком, но основанной на несколько измененной эвристике (см. Х А)8ог1»Ьтэ Т (1986), 159-173): 9 ° 2' — 9 2'~»+1, если э четно; (11) 8 ° 2' — б 21'+0~» + 1, если э нечетно. Седгевик доказал, что, когда используются сформированные по этому правилу смещения (Ьо, Ьм Ьэ,... ) = (1, 5, 19, 41, 109, 209,... ), время выполнения в худшем случае не превышает О(А'»~~). Минимальное число перемещений, 6600, наблюдается для смещений вида 2»+ 1, а также в последовательностях Инсерпи и Седгевика при р = 2. Но важно понимать, что надо учитывать не только число перезаписей, хотя именно оно асимптотически доминирует в общем времени работы.
Так как время выполнения программы П равно 9В+ 10КТ+ ° " единиц (машинных циклов), ясно, что экономия одного прохода примерно эквивалентна сокращению числа перезаписей на — 'еМ; при Ю = 1000 целесообразнее добавить 1111 перезаписей, если за счет этого удастся сэкономить один проход. Поэтому представляется неразумным начинать с Ь| ы большего, чем, скажем, ~Л, поскольку большое значение смещения не убавит числа последующих перезаписей настолько, чтобы оправдать первый проход. Обширное экспериментальное тестирование, выполненное М. А.
Вайсом (М, А. Же(зэ) (Сошр. Х 34 (1991). 88-9Ц, четко выявило, что среднее число перезаписей, выполняемых в ходе сортировки по алгоритму П при смещениях 2 — 1, ..., 15, 7, 3, 1, примерно пропорционально Х»/4. Если быть более точным, Вайс показал, что Вмч и,' 1.55%»~4 — 4.48% + О(Ф»~») пРи 100 < Ж < 12000000, если использУютсЯ эти смещения; эмпирическое стандартное отклонение составляло примерно .065Ж»~». Он также выяснил, что последовательность Седгевика (11) приводит к асимптотически более высокой производительности, В, - 0.4ЗЬ'"/е + 18.5% + О(Ж»~э).
Удивительно, но стандартное отклонение ддя этой последовательности смещений оказалось довольно мало, примерно Ю~~~. В табл. 7 показаны типовые характеристики числа перезаписей, отнесенные к одному проходу, которые были получены в трех экспериментах со случайными данными. Использовалась последовательность смещений вида 2 — 1, 2 + 1 и (11). В каждом эксперименте использовались те же массивы данных. Общее число перезаписей 2,', В, в этих экспериментах оказалась равным соответственно 346 152, 329 532 и 248 788, так что первенство в этих "соревнованиях" следует отдать последовательности (11).
Хотя с каждыл» новым экспериментом мы все глубже проникаем в тайны сортировки по алгоритму Р, три десятилетия исследований не дали окончательного ответа на главный вопрос — какая последовательность смещений наилучшая. Если Ю меньше 1 000, самое простое правило наподобие Положить Ье = 1, Ьэе» вЂ” — ЗЬэ + 1 и остановиться ла Ь|» при ЗЬ| > Л (12) Таблица 7 кОличестВО пеРезАписей нА пРОхОд: Эксперименты пРи м = 20000 л, в, л, в, 3905 20714 2161 13428 929 18206 505 16444 209 21405 109 19605 41 26604 19 23441 5 38941 1 50000 4097 19459 2049 14852 1025 15966 513 18434 257 22746 129 27595 65 34528 33 45497 17 48717 9 38560 5 20271 3 9448 1 13459 4095 19458 2047 15201 1023 16363 511 18867 255 23232 127 28034 63 33606 31 40350 15 66037 7 43915 3 24191 1 16898 оказывается не хуже любого другого.
Но для больших значений 1У можно рекомендовать последовательность Седгевика (11), которая обрывается на Л| м если ЗЛ,>Ф. В упр. 43 продемонстрировано, как удалить проверку 1 > 0 на шаге 05. Это изменение позволяет ускорить сортировку примерно на 10%. Вставки в список. Оставим теперь метод Шелла н рассмотрим другие пути усовершенствования метода простых вставок. Среди общих способов улучшения алгоритма один нз самых важных основывается на тщательном анализе структур данных, поскольку реорганизация структур данных, позволяющая избежать ненужных операций, часто дает существенный эффект. Длльнейшее обсуждение этой общей иден можно найти в разделе 2.4, в котором рассматривается довольно сложный алгоритм.
Посмотрим, как она применяется к такому нехитрому алгоритму, как простые вставки. Какова наиболее подходящая структура данных для алгоритма 37 Сортировка методом простых вставок состоит из двух основных операций: 1) просмотра упорядоченного массива для нахождения наибольшего ключа, меньшего илн равного данному ключу; й) вставки новой записи в определенное место упорядоченного массива. Массив — это, очевидно, линейный список, н алгоритм о' обрабатывает его, используя последовательное распределение (раздел 2.2.2); поэтому для выполнения каждой операции вставки необходимо переместить примерно половину записей.
С другой стороны, нам известно, что для вставок идеально подходит хранение данных в памяти в виде связного списка 1раздел 2.2.3), так как прн этом требуется изменить лишь несколько связей; другая операция — последовательный просмотр — при использовании связного списка по*гги так же проста, как и при последовательном размещении данных. Поскольку списки всегда просматриваюогся в одном и том же направлении, достаточно иметь списки с однонаправленной связью. Таким образом, приходим к выведу, что "правильная" структура данных для метода простых вставок — линейные списки с однонаправленными связямн.
Целесообразно также изменить алгоритм Б, чтобы список просматривался в порядке возрастания. Алгоритм Ь (Мемед всп»авкн в сансов). Предполагается, что записи Вы..., В~ч содержат ключи К„...,КИ н поля связи Хы..., Ьм, в которых могут храниться числа от О до Ф; имеется также еще адно поле связи Ьо в некоторой искусственной записи Во в начале массива. Алгоритм устанавливает поля связи твк, что записи оказываются связанными в порядке возрастания. Так, если р(Ц...р(1»') — "устойчивая" перестановка, такая, что Кр111 « .. Крумм то и результате применения алгоритма получим .Хо = р(1); Ьрр0 = р(»+ 1) при 1 <» < А~; Ьр(Ф1 = О.
(13) Ь1. (Цикл по»'.] Присвоить Х,о»- г7, Х, »»- О. (Хо служит "головным" элементом списка, а Π— пустой связью; следовательно, список, по существу, циклический.) Выполнить шаги от 12 до Ьб при» = М-1, Х-2, ..., 1 и завершить процелуру. Ь2. (Углвновкар,б, К.] Присвонтьр»- Хо,б»- О, К»- К . (На последующих шахах запись В будет вставлена в нужное место в связном списке путем сравнения ключа К с предыдущими ключами в порядке возрастания, Переменные р и ц служат указателями на текущее место и списке, причем р = Х», так что 9 всегда на один шаг отстает от р.) ЬЗ. (Сравнение К: Кр.] Если К < Кр, то перейти к шагу 1,5.
(Найдено искомое положение записи В в списке между В» и Вр.) Ь4. (Продвинуть р, 9,] Присвоить 9»- р, р +- Х,». Если р > О, то возвратиться к шагу ЬЗ. (Если р = О, то К вЂ” наибольший ключ, обнаруженный до снх пор; следовательно, запись В должна попасть в конец списка, между В» и Во.) Ьб [Вставка В список ] Присвоить Х» + Я~ ЬХ + р $ Этот алгоритм важен не только потому, что он является простым методом сортировки, но и потому, что он часто входит в состав других алгоритмов обработки списков. В табл.
8 показано несколько первых шагов сортировки шестнадцати чисел, выбранных нами для примеров. Таблица Е ПРИМЕР РЕАЛИЗАЦИИ МЕТОДА ВСТАВКИ В СПИСОК У: 0 1 2 3 4 5 6 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 Хв: 16 0 15 Ь',: 14 - - - - - 16 0 15 Программа 1 (Метод во»лавки в список). Предполагаеты„что ключ К1 хранится по адресу 1ИРОТ+1(О:3), а Ьт хранится по адресу 1ИРОТ+г(4:5). Значения в регистрах таковы: г11 ги»; г12»в р; г13»в в; гА(0: 3) га К. 01 КЕХ ЕОО О: 3 08 Ь1ИЕ ЕОО 4: б Ж>1>1.'! 08 БТАНТ 04 Об Об 07 2Н 08 00 10 ЗН 11 1З 4Н 10 14 1б 5Н 10 17 6Н 10 ЕИТ1 И Бт1 ХНРОТ(ьтик) Бтз ХИРОТ+и(ьтик) 1ИР 6Р ьо2 хинт(ьтик) еитз о ЬОА ХИРОТ,1 СИРА ХИНТ„2(КЕУ) ЛЬЕ 5Р еитз 0,2 ЬР2 ХИРОТ,З(1.|ИК) 12Р ЗВ БТ1 ХИРУТ,З(ЬХИК) БТ2 ХИНТ,1(Ь1ИК) ОЕС1 1 11Р 2В 1 1 1 1 )У вЂ” 1 51 — 1 )У вЂ” 1 В + Хт' — 1 — .4 В+ 1Ч' — 1 — А В В В 1Ч вЂ” 1 Ф вЂ” 1 К 1н Н.Л ~1 ~ Н.
Х,<-Д. Ьл <-О. Переход иа уменьшение 1. ~ 2Ъ~ьн~д~,х г ь. д е- О. К+- К1. ЬЗ. С авннть К: К . Перейти к шагу 1.5, если К < Кр. Р +-Ь,. Перейти к шагу ЬЗ, если р > О. Ьб. В т нть и спи ок. Ь, е- 1. Х. ь-Р. Время выполнения этой программы равно 7В+ 14К - ЗА -б машиииых циклов, где Хт' — длина массива, А+ 1 — число правостороииих максимумов, а В что инверсий в исходной перестановке. (С)ь с аиализоч программы Я. Обратите внимание, что программа Ь ие перемещает записи в памяти; это можно сделать, как в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
