AOP_Tom3 (1021738), страница 112
Текст из файла (страница 112)
Некоторые методы сортировки предполагают существование величии "со" и "— оо" или одной из них. Величина "со" считается больше, а величина "— оо" меньше любого ключа: для 1 < Е' < К. — оо < Ку < со Эти величины используются в качестве искусственных ключей, а также граничных признаков. Равенство в (3), вообще говоря, исключено. Если же оно, тем не менее, допускается, алгоритмы можно модифицировать так, чтобы онн все-таки работали, хотя нередко прн этом их изящество и эффективность отчасти утрачиваются.
Обычно методы сортировки подразделяют на два класса; внутренние, когда все записи хранятся в быстрой оперативной памяти, и внешние, когда все записи в ней не помещаются. Методы внутренней сортировки обеспечивают болыпую гибкость при построении структур данных и доступа к ним, внешние же методы обеспечивают достижение нужного результата в "спартанских" условиях ограниченных ресурсов. Достаточно хороший общий алгоритм затрачивает на сортировку Х записей врс мя пропорционально Х !ок К; при этом требуется около !ок Х "проходов" по данным.
Как мы увидим в разделе 5.3.1, это минимальное время, если записи рвсположены в произвольном порядке н сортировка выполняется попарным сравнением ключей. Так, ею~и удвоить число записей, то и время при прочих равных условиях возрастет немногим более чем вдвое. (На самом деле, когда )У неограниченно возрастает, время сортировки растет как Аг(!ойАг)г, если все ключи различны, поскольку и размеры ключей увеличиваются, как минимум, пропорционально !оя )У с ростом гУ; но практически Х всегда остается ограниченным.) С другой стороны, если известно, что ключи являются глучайными величинами с некоторым непрерывным распределением, то, как мы увидим ниже, сортировка может быть выполнена в среднем за 0()т') шагов. УПРАЖНЕНИЯ (часть 1) 1.
(М20) Докажите, что из законов трихотомии и транэитивности вытекает единстеениистпь перестановки р(1) р(2)... р(К), если сортировка устойчива. 2. (21] Пусть каждая запись йз некоторого файла имеет дев ключа: "большой ключ" К, и "малый ключ" й, причем оба множества ключей линейно упорядочены. Тогда можно обычным способом ввести яекспкографическпй порядок на множестве пар ключей (К, к): (К,,>с,) < (Кз,й,), если К, < К, илн К, = К, и ~с, < ~с,.
Алиса рассортировала этот файл сначала по большим ключам, получив и групп записей с одинаковыми большими ключами в каждой группе: К„„= " = К„п, < Кжп П - " — К„О,> « " К„О„„Н = " = К„,„ь где г„= Х. Затем она рассортировала каждую иэ и групп Вжч .<.В,...,йрп ! по собственным малым ключам. Билл взял тот же исходный файл и сначала рассортировал его по малым ключам, а затем получившийся файл рассортировал по большим ключам.
Взяв тот же исходный файл, Крис рассортировал его один раз в лексикографнческом порядке, пользуясь парами ключей (К,, !гг). Получилось ли у всех троих одно и то жеу 3. [Мрб) Пусть на множестве Км ..,, Кл определено отношение "<", для которого закон трихотомии выполняется, а закон траизитивности — нет.
Докажите, что и в этом случае возможна устойчивая сортировка записей„т. е. сортировка, при которой выполняются условия (1) и (2). (На самом деле существует, по крайней мере, три расположения записей, удовлетворяющих этим условиям!) 4. (21) Составители словарей фактически не следуют жестко лексикографическому порядку, так ках прописные и строчные бухвы у них перемежаются. В частности, используется такой порядок: а < А~аа < АА < ААА < Аасбеп < ааЬ < < хвг < ЕЕЕ.
Поясните, как реализовать подобный словарный порядок сортировки. б. [Адйд) Разработайте двоичный код для всех неотрицательных целых чисел, такой, что, если и закодировано в виде строки р(п), то гп < и тогда и только тогда, когда р(т) меньше в лексикографическом смысле, чем р(п). Более того, р(т) не дшгжно быть префиксом р(п) для любого т ф и. По возможности длина р(п) должна быть по крайней мере 1Е и + 0(1оЕ1оБ и) для всех больших и. (Тахой способ кодирования очень удобен. если приходится сортировать текст, состоящий из чисел и слов, или если желательно отобразить довольно большие текстовые последовательности на двоичные коды.) В.
(15) Программисту на И1Х Б. С. Двллу потребовалось выяснить, находится ли в ячейке А число, болыпее числа вз ячейки В, меньшее или же равное ему. Он напигал в программе "ЬОА А; БОВ В'. а потом проверил, какой результат получился в регистре А: положительный, отрицательный или нуль. Какую серьезную ошибку он допустил и как должен был поступить? 7. '„17) Напишите подпрограмму для компьютера И1Х для сравнении ключей с увеличенной точностью, исходя из следующих условий.
Вызов. 1ИР СОИРАВЕ Состояние при входе гП = и; СОМТЕМТБ(А + )г) = ал и СОМТЕМТБ(В + А) = Ьл для 1 < А < п, полагается,что и > 1. Состояние при выходе С1 = СИЕАТЕВ, если (а„,...,ал) > (Ь„, ,Ь1); С1 = ЕЦОА1., если (а„ ,а~) = (Ь ,...,Ь!); С1 = 1.ЕБ5, если (а„,,а|) < (Ь,,Ь|); гХ и г11, возможно, изменились. Здесь отношение (а„,, а~) < (Ь„,..., Ь1) обозначает лексикографическое упорядочеяие слева напРаво, т е. сУществУет индекс 1. такой, что ал = Ьл длЯ и > )г > 1, ио аг < Ьм Б. (УО) В ячейках А и В содержатся соответственно числа а и Ь. Похажите, что можно написать программу для И1Х, которая вычисляла бы пцп(а,Ь) и записывала результат в ячейку С, ие пользуясь командами перехода.
(Предостережение. Поскольку арифметическое переполнение невозможно обнаружить без операторов перехода, разул1но так построить программу, чтобы переполнение не могло возникнуть ни при каких значениях а и Ь.) 9. (М57) Какова вероятность того, что после сортировки в порядке неубывания п независил~ых равномерно распределенных на отрезке (О, 1) случайных величин г-е от начала число окажется < х? УПРАЖНЕНИЯ (часть 2) В каждом из этих упражнений поставлена задача, с которой мажет столкнутьси программист.
Предложите хорошее решение задачи, предполагая, что вм иялеете дело с "музейным" компьютерам, у катарогв имеется сравнительно неболЬшая оперативная память, порядка иесхаяьхих тысяч слов и охало полудюжины накопителей на ллагнитной ленте (Н)г?Л) — этого количества вполне достаточно для выполнения сортировки. Алгоритм, который сможет эффективно работать в таких "спартанских" условиях, тем более будет прекрасно выполнять задачу на современных компьютерах. 10. (15] Имеется лента, на которой записан миллион слов данных.
Как определить, сколько на этой ленте различных слов? 11. ]18] Вообразите себя в роли Управлении внутренних доходов Министерства финансов США. Вы получаете миллионы информационных карточек от оргаяизаций о том, сколько денег они выплатили различным лицам. и миллионы налоговых деклараций (карточек) а доходах от налогоплательщиков. Как бы вы стали отыскивать людей, которь1е сообщили не обо всех своих доходах? 12. [М25] (Транспанироеаиие матрицы ) Илгеется магнитнаи лента, содержащая миллион слов, которые представляют собой элементы матрицы 1000 х 1000, записанные по стракач: а1л аьг .. а~лоос аг ю,, аэлооо .. а)аоалаао.
Ваша задача — получить ленту, иа которой элементы этой матрицы были бы записаны по столбцам: а1 ~ аэл ашаа 1 а~ г .. а1еаод ...а~оаолаоо (Погтарайтесь сделать не более десяти просмотров данных.) 13. ]М26] В вашем распоряжении есть довольно большой файл из Аг слав. Как бы вы его "перетасовали" случайным образом? 14. (ЯО] Вы работаете с двумя вычислительными системами, в которых па-разному упорядочены литеры (буквы и цифры).
Как заставить первую систему сортировать файлы с буквенно-цифровой информацией, предназначенные для использования ва второй системе? 15. (18] Имеется довольно больиюй список людей, родившихся в США, с указанием штата, в котором они родились. Как подсчитать тех, кто родился в каждом штатс? (Предполагается, что ни один человек не указан в списке более одного раза.) 16.
]60] Чтобы облегчить внесение изменений в большие программы, написанные на языке ГОКТКАУ, желательно написать программу, которая формирует таблицу перекрссшиь~х ссылая. Входными данными для нее служит программа на ГОКГКА~, а в результате получается листинг исходной программы, снабженный укаэате.тем всех случаев употребления каждого идентификатора (т.
е. имени) в программе. Как написать такую программу? ь 17. ]УЗ] (Сортировка библиагра4ических каргоачек кашалага ) До появления компьютерных баз данных в каждой библиотеке существовал каталог библиографических карточек, с полющью которого читатели могли отыскать интересующие их издания. Но сортировка карточек в порядке, удобном для читателей, усложняется по мере увеличения библиотечного фонда.
В следующем "алфавитном" списке содержатся рекомендации, взятые из правил регистрации н хранении каталожных карточек Американской библиотечной ассоциации (Чикаго, 1942). 2Ькст коржачки К. Ассы!еш)а пах!опа1е бе! 1лпсег, Когпе 1612; е!и Л)в!от)эсЬег Когвап В!Ы)агЛЛг!ие г!'Ь)агапе гечо)ц!)папа)ге В!Ы!агЛЬг!ие г!ев сапов!гев Вгов'и, Ыгв. З. СгоэЬу Вгоч и, ЗоЛп Вговп, ЗоЬп, шагЬегпаг)с)аа Вгошп, ЗоЬп, оГ Воя!оп Вгоша, ЗоЬп, 1715-1766 ВКО11гХ. ЗОНУ, 1715 — 1766 Вговп, ЗоЛп, г!. 1611 Замечания В названиях иностранных (кроме британских) учреждений слово "гоуа)су" (королевский) игнорируется АсЬгхеЬпЬапбег!кшб!Г (числительное 1612 на немецком языке) В французском тексте апостроф рассматривается как пробел Диатоническне знаки игнорируются Указание положения (Мгэ.) игнорируется Фамилии с датами следуют за фамилиями без дат ..., которые упорядочиваются по описательным славам Одинаковые фамилии упорядочиваются по датам рождения Работы о нем идут после его работ Иногда год рождения определяется приблизи- тельно Текст карточка Вговай Пг.
уо1гп, 1810-1882 Вгони-Ч Ийашя, Кейбла!д Майереасе Вгои п Ашепса Вгоа п й 1>аИ!яоп'я Хегаба гГ!гесгогу Вгов п1о!гп, А!ап Гуеп', Ч!айш!г Ег!пагдог!сЬ, 18б7— ТЛе г!еп Г)еп ИеЬеп !апбеп Таб Г!!х, Могбап, 1827-1908 1812 опгегспге 1 е Х!Хе я!ес!е Ггапча!я ТЬе 1847 тяпе оГ ! .Б. ягашря 1812 океггпге 1 аш а гаагЬешаг!с!ял 1ВМ 1ошпа! оГ геяеагсЬ апг! беге!оршепг Ьа-1 Ла-еЬаб 1а: а !оге аготу 1пгегпабопа! Вая!пеяя МасГйпея Согрогагюп а1-К1шиаг!гшГ, МпЬашшаг! !Ьп Мбяа, )Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
