AOP_Tom3 (1021738), страница 37
Текст из файла (страница 37)
8. Алгоритм Сг подсчет сравнений. Л' > г > О. сг,гг ° ю '. С4 С авнсонс К: К Переход, если К, > Кг. солт[1) +1 -+ солт(13. солт(г) < — сооитбй + 1. дг,к ° Лг > г > 1 > О. ! Время работы этой программы равно 1ЗЛг+ 6А+ 5 — 4 машинных циклов, где Лг — число записей, А -- число способов выбрать 2 предмета из Лг, т. е. (' ) = (Лг~ — Л)/2, а  — число пар индексов, таких, что 1' ( 1 и К > К,. Значит, В— число инверсий перестановки К~ ... Ки; эта величина подробно аназизировалась в разделе 5.1.1 (формулы 5.1.1-(12) и 5.1.1--(13)), в котором было найдено, что для неравных ключей, расположенных в случайном порядке, В = (ппп О, аке (Лг~ — Х)/4 шах (ЛГЯ вЂ” Лг)/2г оет Лг(Лг — 1)(Л'+ 2.5)/6). 03 ВЕС 1 04 51Р 05 ЕМТ1 Об 1МР 07 2Н ЕОА Об 10Х 09 ЗН СИРА 10 10Е 11 ЕОЗ 12 1ИСЗ !Я БТЗ 14 ЗИР ° 15 4Н 1ИСХ 1б БН ЭЕС2 17 12Р 13 БТХ 10 РЕС1 20 1Н ЕИТ2 91 12Р 1 г 2 М 1Р 1ИРПТ,1 СОПИТ,1 1ИРПТ,2 4Р СОПИТ,2 1 СОПИТ,2 БР 1 1 ЗН СОПИТ,1 1 -1.1 2В Лг Ф 1 1 Лг — 1 Л' — 1 А А В В В В А — В А А М вЂ” 1 1Ч вЂ” 1 Лг Лг Следовательно, выполнение программы С занимает от ЗХ~ + 10Х вЂ” 4 до 5.5Хз ч- 7.5Х вЂ” 4 машинных циклов, а среднее время работы находится посередине между этими крайними значениями.
Например, для данных табл. 1 имеем Х = 16, А = 120, В = 41, значит, программа С рассортирует их за время 1129и. Модификация программы С, обладающей несколько иными временными характеристиками, рассматривается в упр. 5. Множитель Х~, которым определяется время работы, свидетельствует о том, что алгоритм С неэффективен при большом Х; при удвоении числа записей время увеличивается в четыре раза.
Поскольку этот метод требует сравнения всех пар ключей (Ко К,), нет очевидного способа исключить зависимость от Хз. Тем не менее дальше в этой главе будет показано, что, используя другую методику, время сортировки для наихудшего случая можно уменьшить до порядка Х!об%. Алгоритм С интересен для нас не эффективностью, а, главным образом, своей простотой; его описание служит примером того стиля, в котором будут описаны более сложные (и более эффективные) методы.
Существует другая разновидность сортировки посредством подсчета, которая дейсшвишельно весьма важна с точки зрения эффективности; она применима в основном в том случае, когда имеется много равных ключей и все они попадают в интервал н < К < е, ширина которого (е — и) невелика. Кажется, что этн ограничения весьма сужают область применения такой модификации, но на самом деле мы увидим немало приложений этой идеи.
Например, если применить этот метод к старшим цифрам ключей, а не ко всем ключам целиком, то файл окажется частично рассортированным, и будет уже сравнительно просто довести дело до конца. Чтобы понять этот принцип, предположим, что все ключи лежат между 1 и 100. Прн первом просмотре файла можно подсчитать, сколько имеется ключей, равных 1, 2,..., 100, а прн втором — расположить записи в соотнетствующих местах области вывода.
В следующем алгоритме (рнс. 9) все это описано более подробно. Алгоритм В (Подсчета распределения). Этот алгоритм сортирует записи Л,, Лм, используя вспомогательную таблицу СОПИТ[и],,СООИТ[в] в предположении, что все ключи — целые числа в диапазоне н < К < е, 1 < ] < Х. На последнем этапе выполнения алгоритма все записи в требуемом порядке переносятся в область вывода Яы..., Яч. Ш. (Сбросить счетчики.) Обнулить все счетчики СООИТ[н]-СООИТ[в]. [12. (Цикл по уд] Выполнить шаг [13 при 1 < у' < Х; затем перейти к шагу Р4. ВЗ. [Увеличить СООИТ[Ку].) Увеличить значение СООИТ[К,] на 1.
Р4. (Накопление.,' (К этому моменту значение СООИТ[1] есть число ключей, равных ь'.) Присвоить СООИТ [1] +- СООИТИ + СООИТ Б — 1] длн 1 = и + 1, н + 2, ..., ю Вб. [Цикл по ],) (Е этому моменту значение СООИТИ есть число ключей, меньших илн равных г, в частности СООИТ [в] = Х.) Выполнить шаг Рб прн у' = Х, Х вЂ” 1, ..., 1 и завершить ныполненне процедуры. ПО. [Вывод В .) Присвоить ь' +- СОПИТ [Кз], Я; +- Лз н СООИТ [К ] ь- 1 — 1. ) Пример использования этого алгоритма рассмотрен в упр. б; программу для И1Х можно найти в упр. 9.
При сформулированных выше условиях, т. е. когда диапазон г — н мвл, эта процедура сортировки работает очень быстро. Рис. 9. Алгоритм Р: подсчет распределения. Сортировка посредством сравнения и подсчета, как в алгоритме С, впервые упоминается в работе Е. Н. Рг(епд, зАСМ 3 (1956), 152, хотя ее автор и не утверждает, что это его собственное изобретение. Подсчет с распределением, как в алгоритме Р, впервые разработан Х. Сьювордом в 1954 году и использовав при поразрядной сортировке, которую мы обсудим позже (см. раздел 5.2.5); этот метод также был опубликован под названием вМаьЬзогР' в работе Ж.
Рецгхе)б, САСМ 3 (1960), 601. УПРАЖНЕНИЯ 1. [18] Будет ли работать алгоритм С, если иа шаге С2 значение 1 будет изменяться от 2 до?О, а не от?О до 2? Что произойдет, если на шаге СЗ значение 1' будет изменяться от 1 до? — 1? 2. [21] Покажите, что алгоритм С работает правильно и при наличии одинаковых ключей. Если Кз = К, и 1 < 1, то где, в конце концов, окажется 1?,: до или после Ри? 3. [21) Будет ли алгоритм С работать правильно, если на шаге С4 заменить проверку "К, < К," проверкой рК, < К,"? 4. [16] Напишите Н1Х-программу, которая "завершит" сортировку, начатую программой С, ваша программа должна поместить ключи в ячейки ООТРОТ+1-ОСТРОТ+М в порядке возрастания. Сколько времени потребуется на это вашей программе? б.
(22) Станет ли программа С лучше в результате следующих изменений? Ввести новую строку 08а; 1МСХ 0,2 Изменить строку 10: 1ОЕ БР Изменить строку 14 ОЕСХ 1 Удалить строку 15. О. [12] Промоделируйте вручную работу алгоритма Р, показывая промежуточные результаты, получаюгдиеся при сортировке 10 записей БТ, ОС, БО, 00, О., 1М, 88, 28, БХ, 44, 10, Бь, БТ, 81, 70, 7М. Здесь цифры это ключи, а буквы сопутствующая информация в записях. 7. [12] Обеспечивает ли алгоритм Р устойчивую сортировку? 8.
[1Б] Будет лн алгоритм Р работать правильно, если на шаге РБ значение 1 будет изменяться от 1 до 1О, а не от 1О до 1? 9. [22] Напишите 91Х-программу для алгоритма Р, аналогичную программе С и упр. 4. Выразите время работы программы в виде функции от А' и (о — и). 10. [22] Предложите эффективный алгоритм, который бы заменил Х величин (К,, 1?и) соответственно величинами (1?р10,..., Лр~я~), если даны значения 1?и..., Кл и перестановка р(1) .. р(?О) множества (1,..., А1).
Постарайтесь использовать как можно меньше памяти. (Эта задача возникает, когда требуется перекомпоновать в памяти записи после сортировки таблицы адресов, не расходуя память на 2Х записей.) 11. (Мв7] Напишите й11-программу лля алгоритма из упр. 10 и проанализируйте ее эффективность.
° 12. (зэ) Предложите эффективный алгоритм перекомпоновки в памяти записей Лм Ля в рассортированном порядке после завершения сортировки списка (см. рнс. 7). Постарайтесь использовать минимум памяти. я 13. (27) Алгоритму Р требуется память для 2% записей Лм..., Ля и Яп..., Яя Покажите, что можно обойтись памятью для )у записей Лп...,Лж если вместо шагов Р5 и Рб использовать другую процедуру расстановки. (Таким образом, задача состоит в том, чтобы разработать алгоритм, который бы перекомпоновмввл записи Лп..., Лл, основываясь на значениях СООКТ(и),..., СООКТЫ после выполнения шага Р4, без использования дополнительной памяти; это, по существу, обобщение задачи, рассмотренной в упр. 10.) 5.2.1.
Сортировка путем вставок Упомянутый в начале раздела 5.2 способ, которым пользуются игроки в бридж, служит базовым для одного из важных семейств методов сортировки. Этот способ предполагает, что перед рассмотрением записи Л предыдущие записи Лг,..., Л уже упорядочены и Л вставляется в соответствующее место. Приняв эту схему в качестве базовой, можно построить несколько любопытных ее модификаций. Метод простых вставок. Простейший метод сортировки посредством вставок можно считать наиболее очевидным. Пусть 1 < 1' < Аг и записи Лг,...,Л, ~ уже размещены так, что К <К « К, (Напомним, что в этой главе через К, обозначается ключ записи Л, ) Будем сравнивать по очереди Кз с Кз ы К, з, ... до тех пор, пока не обнаружим, что запись Лз следует вставить между Л, и Л,~,; тогда подвинем записи Л,чз,..., Л, г на одну позицию вверх и поместим новую запись в позицию 1+ 1. Удобно совмещать операции сравнения и перемещения„перемежая их между собой, как продемонстрировано в следующем алгоритме; поскольку запись Лу как бы "погружается" на положенный ей уровень, этот способ часто называют просепеанием или погрушсением (рис.
10). Рис. 10. Алгоритм Я: сортировка методом простых вставок. Алгоритм Б (Сортировка мешодом простьх вставок). Записи Лм..., Лн переразмен~аются на том же месте. После завершения сортировки их ключи будут упорядочены: К~ < < Ка. 31. (Цикл по 7'.) Выполнить шаги от 52 до 55 при 1' = 2,3,...,Х и после этого завершить выполнение процедуры. Б2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
