Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 22
Текст из файла (страница 22)
Например, для данных табл. 1 имеем Лг = 16, А = 120, В = 41, значит, программа С рассортирует их за время 1129и. Модификация программы С, обладающей несколько иными временными характеристиками, рассматривается в упр. 5. Множитель Л'~, которым определяется время работы, свидетельствует о том, что алгоритм С неэффективен при большом Л'; при удвоении числа записей время увеличивается в четыре раза. Поскольку этот метод требует сравнения всех пар ключей (К,, К ), нет очевидного способа исключить зависимость от ЛГ~. Тем не менее дальше в этой главе будет показано, что, используя другую методику, время сортировки для наихудшего случая можно уменьшить до порядка Лг1ояЛ'.
Алгоритм г, интересен для нас не эффективностью, а, главным образом, своей простотой; его описание служит примером того стиля, в котором будут описаны более сложныг (н более эффективные) методы. Существует другая разновидность сортировки посредством подсчета, которая дейсягвипгельно весьма важна с точки зрения эффективности; она применима в основном в том случае, когда имеется много равных ключей и все они попадают в интервал и < Ку < е, ширина которого (и — и) невелика. Кажется, что этн ограничения весьма сужают область применения такой модификации, но на самом деле мы увидим немало приложений этой идеи.
Например, если применить этот метод к старшим цифрам ключей, а не ко всем ключам целиком, то файл окажется частично рассортированным, и будет уже сравнительно просто довести дело до конца. Чтобы понять этот принцип, предположим, что все ключи лежат мелгду 1 и 100. При первом просмотре файла можно подсчитать, сколько имеется ключей, равных 1, 2,..., 100, а при втором — расположить записи в соответствующих местах области вывода. В следующем алгоритме (рис. 9) все это описано более подробно. Алгоритм 11 (Подсчета распределения).
Этот алгоритм сортирует записи Нг,..., Яя, используя вспомогательную таблицу СООМТ[и3,..., СООИТ[и] в предположении, что все ключи — целые числа в диапазоне и < К. < е, 1 < 3 < Лг. На последнем этапе выповнения алгоритма все записи в требуемом порядке переносятся в область вывода Яг,, Яя. 331. [Сбросить счетчики.) Обнулить все счетчики СООИТ[и)-СООМТ[е3.
О2. (Цикл ио г,) Выполнить шаг ПЗ при 1 < 3 < Лг, затем перейти к шагу 04. 113. [Увеличить СООИТ[К13.) Увеличить значение СООМТ[К13 на 1. 114. (Накопление.) (К этому моменту значение СООМТ[г3 есть число ключей, равных 1.) Присвоить СООИТ[г3 СООМТ[г3+СООМТН-13 для г = и+1, и+2, ..., е. О5. (Цггкл по у'.) (К этому моменту значение СООМТ[П есть число ключей, меныпих или рваных г', в частности СООИТ Ы = Лг.) Выполнить шаг Рб при,у = Л", Лг — 1, ..., 1 и завершить выполнение процедуры. Вв. (Вывод Лу.) Присвоить г'+- СООИТ[кг3, 5г Ф- В» и СООМТ[кг3 г- г' — 1. $ Пример непользования этого алгоритма рассмотрен в упр. 6; программу для М11 можно найти в упр.
9. При сформулированных выше условиях, т. е. когда диапазон г — и мал, зта процедура сортировки работает очень быстро. Рис. 9. Алгоритм О: подсчет распределения. Сортировка посредством сравнения и подсчета, как в алгоритме С, впервые упоминается в работе Е. Н. гг)епд, зАСМ 3 (1956), 152, хотя ее автор и не утверждает, что зто его собственное изобретение. Подсчет с распределением, как в алгоритме О, впервые разработан Х. Сьювордом в 1954 году и использован при поразрядной сортировке, которую мы обсудим позже (см.
раздел 5.2.5); этот метод также был опубликован под названием "Мас)ззогс" в работе тт'. гепгзе)б, САСМ 3 (1960), 601. УПРАЖНЕНИЯ 1. [16] Будет ли работать алгоритм С, если на шаге С2 значение 1 будет изменяться от 2 до 1У, а не от )т" до 2? Что произойдет, если на шаге СЗ значение у будет изменяться от 1 до 1 — 1? 2, [81] Покажите, что алгоритм С работает правильно и прн наличии одинаковых клю- чей. Если Ку = К, и,у < 6 то где, в конце концов, окажется В,: до или после В~? 2. [81] Будет ли алгоритм С работать правильно, если на шще С4 заменить проверку "К; ( К," проверкой "К; < К1"? 4.
[16) Напишите ИХХ-программу, которая "завершит" сортировку, начатую программой С; ваша программа должна поместить ключи в ячейки 00ТРБТ+1-00ТРСТ+И в порядке воз- растанпя, Сколько времени потребуется на зто вашей программе? Ь. [ВВ] Станет ли программа С лучше в результате следующих изменений? Ввести новую строку 08а: ХИСХ 0,2 Иэмейнть строку 10: 10Е БР Изменить строку 14: 0ЕСХ 1 Удалить строку 15, 6. [1В] Промоделируйте вручную работу алгоритма О, показывая промежуточные ре- зультаты, получающиеся прн сортировке 16 записей БТ, ОС, 60, 00, 9., 1И, 86, 2И, 61, 44, 10, Я., БТ, 61, 70, 7И. Здесь цифры — это ключи, а буквы — сопутствующая информация в записях.
Т. [1В] Обеспечивает ли алгоритм О устойчивую сортировку? 8. [15] Будет ли алгоритм О работать правильно, если на шаге ОБ значение 1 будет изменяться от 1 до 1У, а не от Ю до 1? 9. [ВВ] Напишите ИХХ-программу для аж орнтма О, аналогичную программе С и упр. 4. Выразите время работы программы в виде функции от ?У и (е — в). 10. [ВБ] Предложите эффективный алгоритм, который бы заменял 1т' величин (Вм..., Вл) соответственно величинами (Ври..., Вг1л1), если даны значения Вм., ., Вл и пере- становка р(1)... Р(1г') множества [1,..., ?И). Постарайтесь использовать как можно меньше памяти.
(Эта задача возникает, когда требуется перекамзюновать в памяти записи после сортира зки таблицы адресов, не расходуя память на 2Ю записей.) 11. (МЯ7) Напишите йХХ-программу длн алгоритма мз упр. 10 и проанализируйте ее эффективность. ° 12. [Я5) Предлажпте эффективный алгоритм перекомпановки в памяти записей Ви..., В» в рассортированном парилке после завершения сортировки списка (см. рис. 7). Постарайтесь использовать минимум памяти. ь 13, (э7) Алгоритму П требуется память лля 2М записей Ви, ..,В» и Яи...,5». Показкнте, что можно обойтись памятью для Х записей Ви..., Я», если вместо шагсе Пб н 116 использовать другую процедуру расстановки.
(Таким образом, задача состоит в том, чтобы разработать «лгаритм, который бы перекомпоновывал записи Лз,,В», основываясь на значениях СССВТЫ,..., СССЭТЫ после выполнения шага О4, без непользования дополнительной памяти; это, по существу, обобщение залечи, рассмотренной в упр.
10.) $.2.1. Сортировка путем вставок Упомянутый в начале раздела 5.2 способ, которым пользуются игроки в бридж, служит базовым для одного из важных семейств методов сортировки. Этот способ предполагает, чта перед рассмотрением записи В предыдущие записи Вз,..., В. з уже упорядочены и В вставляется в соответствующее места. Приняв эту схему в качестве базовой, можно построить несколько любопытных ее пацификаций. Метод простых вставок. Простейший метод сортировки посредством вставок можно считать наиболее очевидным.
ПУсть 1 <,1 < М и записи Вз,...,Вз з Уже размещены так, чта Кз <Кт « ° ° К (Напомним, что в этой главе через Ку обозначается ключ записи В .) Будем сравнивать па очереди Кз с Кз з, К т, ... до тех пор, пока не обнаружим, что запись В следует вставить между Вз и Вььз, тогда подвинем записи Вз~ьз,..., В. з на одну позицию вверх и поместим новую запись в позицию з + 1.
Удобно совмещать операции сравнения н перемещения, перемежая их между собой, как продемонстрировано в следующем алгоритме; поскольку запись В как бы "погрулшется" на положенный ей уровень, этот способ часто называют просеиеонием или погружением (рис. 10). Рис. 10. Алгоритм Я; сортировка методом простых вставок. Алгоритм Б (Сортировка методом просшмх еспзоеок). Записи Вз,...,В» переразмещаются на там же месте. После завершения сортировки их ключи будут упорядочены: Кз « К». 51. [Цззкл по 1.] Выполнить шаги от Я2 до 85 при з = 2,3,...,Ф и поСле этого завершить выполнение процедуры. Б2. ~Установка ь, К, В.) Присвоить | +- у — 1, К +- К, В +- В„. (На последующих шагах будет предпринята попытка вставить запись В в нужное место, сравнивая К с К; при убывающих значениях 4.) БЗ.
~Сравнение К: К;.] Если К > К„то перейти к шагу БЬ. (Мы нашли искомое место для записи В,) Бб. ~Перемещение В;, уменьшение Ц Присвоить Вча +- Вп 1 г- 1 — 1. Если 4 > О, *о вернуться к шагу БЗ. 1Если 4 = О, то К вЂ” наименьший из рассмотренных до снх пор ключей, а значит, запись В должна занять первую позицию.) Бб. ~Перенос В на место В;+1.) Присвоить В,+~ с- В. $ В табл.
1 показан процесс выполнения алгоритма Б на множестве из шестнадцати чисел, которые используются для примеров в этом разделе. Данный метод чрезвычайно просто реализуется программно. На самом деле следующая ИХХ-программа самая короткая из всех "порядочных" программ сортировки в этой книге. Таблица 1 ПРИМЕР СОРТИРОВКИ МЕТОДОМ ПРОСТЫХ ВСТАВОК „503;087 087 503„:Ы2 „087 503 Ы2:061 061 087 503 Ы2„:908 061 087„503 512 908: 170 081 087 170 503 512 908:897 061 037 154 170 275 426 503 509 512 612 653 677 765 897 908: 703 061 087 154 170 275 426 503 509 Ы2 612 653 677 703 765 397 908 Программа Б 1,Сортпироеке меиюдом простиььт еспюеок).
Адреса записей, которые надо рассортйровать, — от ХМРОТ+1 до 1ИРОТ+М: записи сортирукпся в той же области памяти по ключу, занимающему целиком одно слово, Здесь гП гв 7 — К; Н2 ьв ь'; гА = В ьз К; предполагается, что Ф > 2. 01 ЯТАЕТ ЕИТ1 2-И а.льи.иь ~ 03 ЗН 1ВА 1МРОТ+И,1 К вЂ” 1 32, Ъс ака 1 К 03 ЕИТ2 И-1,1 Ю вЂ” 1 1+-,у — 1. 04 Зн ЬИА ХИИ,1 В ж-! —,~ ~~з. * К: ь ь 05 ЗОЕ ЬР В+ Ж вЂ” 1 — А Перейти к шагу 35, если К > К,.
06 4Н ЕВХ 1МРОТ, 2 В И4. Пе мостить меиьшигь А 07 ЗТХ 1ИРОТ+1,2 В В +1 ь- Во 03 ОЕС2 1 В г ь- 1 - 1. ОУ 32Р ЗВ В Перейти к шагу 33, если 1 > О. 10 ЬН ВТА ХИРВТ+1,2 К вЂ” 1 35. В поместить иа место 71 1ИС1 1 л'-1 13 31МР 28 Ф вЂ” 1 2 <У < К, Время выполнения этой программы равно 9В+ 10%-ЗА -9 машинных циклов*, где Ю вЂ” число сортируемых записей, А — число случаев, когда на шаге 84 значение з убывает до О, а Н вЂ” количество перемещений записей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
