Третий том известной монографии одного из крупнейших американских специалистов по программированию Д. Кнута (первый том вышел в издательстве ”Мир” в 1976 г., второй—в 1977 г.) состоит из двух частей: ”Сортировка” и ”Поиск”. В них подробно исследуются различные алгоритмы внутренней и внешней сортировки, изучаются методы поиска информации в таблицах на основе сравнения или преобразования ключей, даются оценки эффективности предлагаемых алгоритмов. Книга снабжена большим количеством задач и примеров разной степени трудности, существенно дополняющих основной текст. От других руководств по программированию книга выгодно отличается строгостью изложения и широким применением математического аппарата. Вместе с тем она доступна студентам первого курса. Знакомство с двумя первыми томами желательно, но не обязательно. Каждый, кто хочет научиться квалифицированно программировать, найдет в ней много полезного. Рассчитана на широкий круг программистов. 20204−022 K 041(01)−78 22 − 78 Редакция литературы по математическим наукам c Перевод на русский язык, ”Мир”. 1978 ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА Д. Э. Кнут хорошо знаком советскому читателю по переводам двух первых томов его обширной монографии ”Искусство программирования для ЭВМ” и не нуждается в аттестации. Настоящая книга представляет собой третий том и посвящена алгоритмам сортировки и поиска информации. Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Написано немало отчетов, статей, монографий. И даже в этих условиях книга Д. Кнута стала событием. По существу это энциклопедия, в которой можно найти любую справку, касающуюся алгоритмов, методов их оценок, истории вопроса и нерешенных проблем. Нет нужды говорить о важности самой области. Практически сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому, как справедливо отмечает автор, книга адресована не только системным программистам, занимающимся разработкой программ сортировки и поиска информации. Можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства программирования. Кроме теоретической и практической ценности, книга имеет большое методическое значение. Многие авторы и преподаватели смогут извлечь из нее новые и полезные сведения не только по существу рассматриваемых вопросов, но и по способу их изложения. Автору мастерски удается ”расслоить” весь материал таким образом, что книгу можно использовать практически на любом уровне знакомства с предметом и при различной общей математической подготовленности читателя. Перевод выполнен по изданию 1973 г. (первая редакция) с внесением многих (около 700) исправлений и добавлений, любезно предоставленных автором. Разделы с 5.1 по 5.3.2 переведены Н. И. Вьюковой; разделы с 5.3.3 по 5.5 и предисловие— А. Б. Ходулевым; главу 6 перевел В. А. Галатенко. Ю. М. Баяковский В. С. Штаркман ПРЕДИСЛОВИЕ Кулинария стала искусством, высокой наукой; повара теперь—благородные люди. Тит Ливий, АЬ Urbe Condita, XXXIX.vi (Роберт Бертон, Anatomy of Melancholy, 1.2.2.2)1 Материал этой книги логически продолжает материал по информационным структурам, изложенный в гл. 2, поскольку здесь к уже рассмотренным концепциям структур добавляется понятие линейно упорядоченных данных. Подзаголовок ”Сортировка и поиск” может привести к мысли, что эта книга предназначена лишь для системных программистов, занимающихся построением универсальных программ сортировки или связанных с выборкой информации. Однако в действительности предмет сортировки и поиска дает нам прекрасную основу для обсуждения широкого класса важных общих вопросов: Как находить хорошие алгоритмы? Как улучшать данные алгоритмы и программы? Как исследовать эффективность алгоритмов математически? Как разумно выбрать один из нескольких алгоритмов для решения конкретной задачи? В каком смысле можно доказать, что некоторые алгоритмы являются ”наилучшими из возможных”? Как теория вычислений согласуется с практическими соображениями? Как эффективно использовать различные виды внешней памяти—ленты, барабаны, диски—для больших баз данных? Я думаю, что на самом деле в контексте сортировки и поиска встречается практически любой важный аспект программирования. Настоящий том состоит из гл. 5 и 6 монографии. В гл. 5 рассматривается сортировка (упорядочение); это очень большая тема, она разбита на две главные части—внутреннюю и внешнюю сортировку. В эту главу входят также дополнительные разделы, развивающие вспомогательную теорию перестановок (§ 5.1) и теорию оптимальных алгоритмов сортировки (§ 5.3). В гл. 6 мы имеем дело с поиском определенного элемента в таблице или файле; содержимое этой главы подразделяется на Роберт Бертон (1577–1640) — английский ученый, писатель и теолог. Прим. Перев. методы последовательного поиска, методы поиска со сравнением ключей, поиска с использованием свойств цифр, поиска с помощью ”хеширования”; затем рассматривается более сложная задача выборки по вторичным ключам. Обе главы поразительно тесно переплетаются между собой, между их предметами имеются близкие аналогии. В дополнение к гл. 2 рассматриваются два важных вида информационных структур, а именно приоритетные очереди (п. 5.2.3) и линейные списки, представляемые посредством сбалансированных деревьев (п. 6.2.3). Читателю, не знакомому с первым томом этой монографии, рекомендуется обращаться к указателю обозначений (приложение В), так как некоторые из встречающихся в книге обозначений не являются общепринятыми. Эта книга без большей части математического материала была использована мной в качестве учебника по второму курсу лекций ”Структуры данных” для студентов младших и средних курсов. Математические части этой книги, особенно § 5.1, п.5.2.2, § 6.3 и 6.4, могли бы составить учебник по анализу алгоритмов для студентов средних и старших курсов. Кроме того, на основе п. 4.3.3, 4.6.3, 4.6.4, § 5.3 и п. 5.4.4 можно построить курс лекций ”Сложность вычислений” для старшекурсников. Быстрое развитие информатики и вычислительных наук задержало выход в свет этой книги почти на три года, поскольку очень многие аспекты сортировки и поиска подвергались детальной разработке. Я очень благодарен Национальному научному фонду, Отделению военно-морских исследований, Институту обороны, фирмам IBM и Norges Almemitenskapelige Forskningsrad за постоянную поддержку моих исследований. В подготовке этого тома к печати мне оказали помощь многие лица, особенно Эдвард А. Бендер, Кларк Э. Крэйн, Дэвид Э. Фергюсон, Роберт У. Флойд, Рональд Л. Грэхем, Леонидас Гюиба, Джон Хопкрофт, Ричард М. Карп, Гэри Д. Кнотт, Рудольф А. Крутар, Шень Линь, Воган Р. Пратт, Стефан О. Райе, Ричард П; Стэнли, Я. А. ван дер Пул и Джон У. Ренч мл., а также студенты Стэнфорда и Беркли, которым пришлось искать ошибки в рукописи. Д. Э. Кнут сентябрь 1972 Осло, Норвегия, Писатель пользуется известными привилегиями, в благодетельности которых, надеюсь, нет никаких оснований сомневаться. Так, встретив у меня непонятное место, читатель должен предположить, что под ним кроется нечто весьма полезное и глубокомысленное.2 (Джонатан Свифт, ”Сказка бочки”, предисловие, 1704) ЗАМЕЧАНИЯ ОБ УПРАЖНЕНИЯХ Упражнения, помещенные в книгах настоящей серии, предназначены как для самостоятельной проработки, так и для семинарских занятий. Трудно, если не невозможно изучить предмет, только читая теорию и не применяя полученную информацию для решения специальных задач и тем самым не заставляя себя обдумывать то, что было прочитано. Кроме того, мы лучше всего заучиваем то, что сами открываем для себя. Поэтому упражнения образуют важную часть данной работы; были предприняты определенные попытки, чтобы отобрать упражнения, в которых бы содержалось как можно больше информации и которые было бы интересно решать. Во многих книгах легкие упражнения даются вперемешку с исключительно трудными. Зачастую это очень неудобно, так как перед тем, как приступать к решению задачи, читатель обязательно должен представлять себе, сколько времени уйдет у него на это решение (иначе он может разве только просмотреть все задачи). Классическим примером здесь является книга Ричарда Беллмана ”Динамическое программирование”; это важная пионерская работа, в которой в конце каждой главы под рубрикой ”Упражнения и исследовательские проблемы” дается целый ряд задач, где наряду с глубокими еще нерешенными проблемами встречаются исключительно тривиальные вопросы. Говорят, что однажды кто-то спросил д-ра Беллмана, как отличить упражнения от исследовательских проблем, и тот ответил: ”Если вы можете решить задачу, это—упражнение; в противном случае это—проблема”. Можно привести много доводов в пользу того, что в книге типа этой должны быть как исследовательские проблемы, так и очень простые упражнения, и для того чтобы читателю не приходилось Перевод А. А. Франковского.—Прим. Перев. ломать голову над тем, какая задача легкая, а какая трудная, мы ввели ”оценки”, которые указывают степень трудности каждого упражнения. Эти оценки имеют следующее значение: Оценка Объяснение 00 Чрезвычайно легкое упражнение, на которое можно ответить сразу же, если понят материал текста, и которое почти всегда можно решить ”в уме”. 10 Простая задача, которая заставляет задуматься над прочитанным материалом, но не представляет никаких особых трудностей. На решение такой задачи требуется не больше одной минуты; в процессе решения могут понадобиться карандаш и бумага. 20 Задача средней трудности, позволяющая проверить, насколько хорошо понят текст. На то чтобы дать исчерпывающий ответ, требуется примерно 15–20 минут. 30 Задача умеренной трудности и/или сложности, для удовлетворительного решения которой требуется больше двух часов. 40 Очень трудная или трудоемкая задача, которую, вероятно, следует включить в план практических занятий. Предполагается, что студент может решить такую задачу, но для этого ему потребуется значительный отрезок времени; задача решается нетривиальным образом. 50 Исследовательская проблема, которая (насколько это было известно автору в момент написания) еще не получила удовлетворительного решения. Если читатель найдет решение этой задачи, его настоятельно просят опубликовать его; кроме того, автор данной книги будет очень признателен, если ему сообщат решение как можно быстрее (при условии, что оно правильно). Интерполируя по этой ”логарифмической” шкале, можно прикинуть, что означает любая промежуточная оценка. Например, оценка 17 говорит о том, что данное упражнение чуть легче, чем упражнение средней трудности. Задача с оценкой 50, если она будет решена каким-либо читателем, в следующих изданиях данной книги может иметь уже оценку 45. Автор честно старался давать объективные оценки, но тому, кто составляет задачи, трудно предвидеть, насколько трудными эти задачи окажутся для кого-то другого; к тому же у каждого человека существует определенный тип задач, которые он решает быстрее. Надеюсь, что выставленные мной оценки дают правильное представление о степени трудности задач, но в общем их нужно воспринимать как ориентировочные, а не абсолютные. Эта книга написана для читателей самых разных степеней математической подготовки и искушенности, поэтому некоторые упражнения предназначены только для читателей с математическим уклоном. Если в каком-либо упражнении математические понятия или результаты используются более широко, чем это необходимо для тех, кого в первую очередь интересует программирование алгоритмов, то перед оценкой такого упражнения ставится буква ”М”. Если для решения упражнения требуется знание высшей математики в большем объеме, чем это дано в настоящей книге, то ставятся буквы ”ВМ”. Пометка ”ВМ” отнюдь не является свидетельством того, что данное упражнение трудное. Перед некоторыми упражнениями стоит стрелка ”>”; это означает, что данное упражнение особенно поучительно и его рекомендуется обязательно выполнить. Само собой разумеется, никто не ожидает, что читатель (или студент) будет решать все задачи, потому-то наиболее полезные из них и выделены. Это совсем не значит, что другие задачи не стоит решать! Каждый читатель должен по крайней мере попытаться решить все задачи с оценкой 10 и ниже; стрелки же помогут выбрать, какие задачи с более высокими оценками следует решить в первую очередь. К большинству упражнений приведены ответы; они помещены в специальном разделе в конце книги. Пользуйтесь ими мудро; в ответ смотрите только после того, как вы приложили достаточно усилий, чтобы решить задачу самостоятельно, или же если для решения данной задачи у вас нет времени. Если получен собственный ответ, либо если вы действительно пытались решить задачу, только в этом случае ответ, помещенный в книге, будет поучительным и полезным. Как правило, ответы к задачам излагаются очень кратко, схематично, так как предполагается, что читатель уже честно пытался решить задачу собственными силами. Иногда в приведенном решении дается меньше информации, чем спрашивалось, чаще—наоборот. Вполне возможно, что полученный вами ответ окажется лучше ответа, помещенного в книге, или вы найдете ошибку в этом ответе; в таком случае автор был бы очень обязан, если бы вы как можно скорее подробно сообщили ему об этом. В последующих изданиях настоящей книги будет помещено уже исправленное решение вместе с именем его автора. Сводка условных обозначений > Рекомендуется М С математическим уклоном ВМ Требует знания ”высшей математики” Требует немедленного ответа Простое (на одну минуту) Средней трудности (на четверть часа) Повышенной трудности. Для ”матпрактикума” Исследовательская проблема Упражнения >1. [00] Что означает пометка ”М20”? 2. [10] Какое значение для читателя имеют упражнения, помещаемые в учебниках? 3. [М50] Докажите, что если n—целое число, n > 2, то уравнение xn + y n = z n неразрешимо в целых положительных числах x, y,z. 5. Сортировка Нет дела более трудного по замыслу, более сомнительного по успеху, более опасного при осуществлении, чем вводить новые порядки. Никколо Макьявелли, ”Государь” (1513) ”Но мы не успеем, просмотреть все номера автомобилей”,—возразил Дрейк. ”А нам и не нужно этого делать, Пол. Мы просто расположим их по порядку и поищем одинаковые”. Перри Мейсон1 . Из ”The Case of Angry Mourner” (1951) Сортировка деревьев с использованием ЭВМ. При таком новом, ”машинном подходе” к изучению природы вы получите возможность быстро распознавать более 260 различных деревьев США, Аляски, Канады, включая пальмы, деревья пустынь и прочую экзотику. Чтобы определить породу дерева, достаточно просто вставить спицу. Каталог ”Edmund Scientific Company” (1964) В этой главе мы изучим вопрос, который часто возникает в программировании: переразмещение элементов в возрастающем или убывающем порядке. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит скорость и простота алгоритмов, предназначенных для их обработки. Хотя в словарях слово ”сортировка” (sorting) определяется как ”распределение, отбор по сортам; деление на категории, сорта, разряды”, программисты традиционно используют это слово в гораздо более узком смысле, обозначая им сортировку предметов в возрастающем или убывающем порядке. Этот процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочением (ordering), но использование этого слова привело бы к путанице из-за перегруженности значениями слова ”порядок”. Рассмотрим, например, следующее предложение: ”Так как только два наших лентопротяжных устройства в порядке, меня призвали к порядку и обязали в срочном порядке заказать еще несколько устройств, чтобы можно было упорядочивать данные разного порядка на несколько порядков быстрее2 . В математической терминологии это слово также изобилует значениями (порядок группы, порядок перестановки, порядок точки ветвления, отношение порядка и т. п.). Итак, слово ”порядок” приводит к хаосу. Перри Мейсон—герой серии детективных романов популярного американского писателя Эрла Стенли Гарднера.— Прим. перев. В оригинале ”Since only two of our tape drives were in working order I was ordered to order more tape units in short order, in order to order the data several orders of magnitude faster”.— Прим. перев. В качестве обозначения для процесса упорядочения предлагалось также слово ”ранжирование”3 , но оно во многих случаях, по-видимому, не вполне отражает суть дела, особенно если присутствуют равные элементы, и, кроме того, иногда не согласуется с другими терминами. Конечно, слово ”сортировка” и само имеет довольно много значений4 , но оно прочно вошло в программистский жаргон. Поэтому мы без дальнейших извинений будем использовать слово ”сортировка” в узком смысле ”сортировка по порядку”. Вот некоторые из наиболее важных применений сортировки: a) Решение задачи ”группировки”, когда нужно собрать вместе все элементы с одинаковым значением некоторого признака. Допустим, имеется 10000 элементов, расположенных в случайном порядке, причем значения многих из них равны; и предположим, нам нужно переупорядочить файл так, чтобы элементы с равными значениями занимали соседние позиции в файле. Это, по существу, задача ”сортировки” в широком смысле слова, и она легко может быть решена путем сортировки файла в узком смысле слова, а именно расположением элементов в неубывающем порядке v1 ≤ v2 ≤ . . . ≤ v10000 . Эффективностью, которая может быть достигнута в этой процедуре, и объясняется изменение первоначального смысла слова ”сортировка”. b) Если два или более файла отсортировать в одном и том же порядке, то можно отыскать в них все общие элементы за один последовательный просмотр всех файлов, без возвратов. Это тот самый принцип, которым воспользовался Перри Мейсон для раскрытия дела об убийстве (см. эпиграфы к этой главе). Оказывается, что, как правило, гораздо экономнее просматривать список последовательно, а не перескакивая с места на место случайным образом, если только список не настолько мал, что он целиком помещается в оперативной памяти. Сортировка позволяет использовать последовательный доступ к большим файлам в качестве приемлемой замены прямой адресации. c) Как мы увидим в гл. 6, сортировка помогает и при поиске, с ее помощью можно сделать выдачи ЭВМ более удобными для человеческого восприятия. В самом деле, листинг (напечатанный машиной документ), отсортированный в алфавитном порядке, зачастую выглядит весьма внушительно, даже если соответствующие числовые данные были рассчитаны неверно. Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, на самом деле она является инструментом, полезным в самых разных ситуациях, и поэтому о нем не следует забывать. В упр. 2.3.2–17 мы обсудили ее применение для упрощения алгебраических формул. Упражнения, приведенные ниже, иллюстрируют разнообразие типичных применений сортировки. Одной из первых крупных систем программного обеспечения, продемонстрировавших богатые возможности сортировки, был компилятор Larc Scientific Compiler, разработанный фирмой Computer Sciences Corporation в 1960 г. В этом оптимизирующем компиляторе для расширенного ФОРТРАНа сортировка использовалась весьма интенсивно, так что различные алгоритмы компиляции работали с относящимися к ним частями исходной программы, расположенными в удобной последовательности. При первом просмотре осуществлялся лексический анализ, т. е. выделение в исходной программе лексических единиц (лексем), каждая из которых соответствует либо идентификатору (имени переменной), либо константе, либо оператору и т. д. Каждая лексема получала несколько порядковых номеров. В результате сортировки по именам и соответствующим порядковым номерам все использования данного идентификатора оказывались собранными вместе. ”Определяющие вхождения”, специфицирующие идентификатор как имя функции, параметр или многомерную переменную, получали меньшие номера, поэтому они оказывались первыми в последовательности лексем, отвечающих этому идентификатору. Тем самым облегчалась проверка правильности употребления идентификаторов, распределение памяти с учетом деклараций эквивалентности и т. д. Собранная таким образом информация о каждом идентификаторе присоединялась к соответствующей лексеме. Поэтому не было необходимости хранить в оперативной памяти ”таблицу символов”, содержащую сведения об идентификаторах. После такой обработки лексемы снова сортировались по другому порядковому номеру; в результате в программе, по существу, восстанавливался первоначальный порядок, если не считать того, что арифметические выражения оказывались записанными в более удобной, ”польской префиксной” форме. Сортировка использовалась и на последующих фазах компиляции—для облегчения оптимизации циклов, включения в листинг сообщений об ошибках и т. д. Короче говоря, компилятор был устроен так, что всю обработку файлов, хранящихся на барабанах, фактически мож3 В оригинале ”sequencing”.—Прим. перев. Это в большей степени относится к английскому слову ”sorting”. Здесь автор приводят пример: ”Не was sort of out sorts after sorting that sort of data”. (Он был как будто не в духе после сортировки такого сорта денных), который в русском переводе не столь выразителен.— Прим. перев. но было вести последовательно. Поэтому-то данные и снабжались такими порядковыми номерами, которые позволяли упорядочивать эти данные различными удобными способами. Другое, более очевидное применение сортировки возникает при редактировании файлов, где каждая строка снабжена ключом. Пока пользователь вносит с клавиатуры изменения и добавления, необязательно держать весь файл в оперативной памяти. Все изменяемые строки можно позднее отсортировать (а они и так обычно в основном упорядочены) и слить с исходным файлом. Это дает возможность разумно использовать память в режиме мультипрограммирования. [Ср. с С. С. Foster, Comp. J., 11 (1968), 134–137]. Поставщики вычислительных машин считают, что в среднем более 25% машинного времени систематически тратится на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Из этой статистики можно заключить, что либо (i) сортировка имеет много важных применений, либо (ii) ею часто пользуются без нужды, либо (iii) применяются в основном неэффективные алгоритмы сортировки. По-видимому, каждое из трех предположений содержит долю истины. Во всяком случае ясно, что сортировка заслуживает серьезного изучения с точки зрения ее практического использования. Но даже если бы сортировка была почти бесполезна, нашлась бы масса других причин заняться ею! Изобретательные алгоритмы сортировки говорят о том, что она и сама по себе интересна как объект исследования. В этой области существует множество увлекательных нерешенных задач наряду с весьма немногими уже решенными. Рассматривая вопрос в более широком плане, мы обнаружим, что алгоритмы сортировки представляют собой интересный частный пример того, как следует подходить к решению проблем программирования вообще. Мы познакомимся со многими важными принципами манипулирования со структурами данных и проследим за эволюцией различных методов сортировки, причем читателю часто будет предоставляться возможность самому ”открывать” те же идеи, как будто бы до него никто с подобными задачами не сталкивался. Обобщение этих частных методов позволит нам в значительной степени овладеть теми способами мышления, которые помогут создавать добротные алгоритмы для решения других проблем, связанных с ЭВМ. Методы сортировки служат великолепной иллюстрацией идей анализа алгоритмов, т. е. идей, позволяющих оценивать рабочие характеристики алгоритмов, а значит, разумно выбирать среди. казалось бы, равноценных методов. Читатели, имеющие склонность к математике, найдут в этой главе немало способов оценки скорости работы алгоритмов и методов решения сложных рекуррентных соотношений. С другой стороны, изложение построено так, что читатели, не имеющие такой склонности, могут безболезненно пропускать выкладки. Прежде чем двигаться дальше, необходимо более четко определить задачу и ввести соответствующую терминологию. Пусть надо упорядочить N элементов R1 , R2 , . . . , RN . Назовем их записями, а всю совокупность N записей назовем файлом. Каждая запись Rj имеет ключ Kj , который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную, ”сопутствующую информацию”, которая не влияет на сортировку, но всегда остается в этой записи. Отношение порядка ”<” на множестве ключей вводится таким образом, чтобы для любых трех значений ключей a, b, c выполнялись следующие условия: i) справедливо одно и только одно из соотношений a < b, a = b, b < a (закон трихотомии); ii) если a < b и b < c, то a < c (закон транзитивности). Эти два свойства определяют математическое понятие линейного упорядочения, называемого еще совершенным упорядочением. Любое множество с отношением ”<”, удовлетворяющим свойствам (i) и (ii), поддается сортировке большинством методов, описанных в этой главе, хотя некоторые из них годятся только для числовых и буквенных ключей с обычным отношением порядка. Задача сортировки—найти такую перестановку записей p(1) p(2) . . . p(N ), после которой ключи расположились бы в неубывающем порядке: Kp(1) ≤ Kp(2) ≤ · · · ≤ Kp(n) . (1) Сортировка называется устойчивой, если она удовлетворяет дополнительному условию, что записи с одинаковыми ключами остаются в прежнем порядке, т. е. p(i) < p(j), если Kp(i) = Kp(j) и i < j. (2) В ряде случаев может потребоваться физически перемещать записи в памяти так, чтобы их ключи были упорядочены; в других случаях достаточно создать вспомогательную таблицу, которая некоторым образом описывает перестановку и обеспечивает доступ к записям в соответствии с порядком их ключей. Некоторые методы сортировки предполагают существование величин ”∞” и ”−∞” или одной из них. Величина ”∞” считается больше, а величина ”−∞” меньше любого ключа: −∞ < Kj < ∞, 1 ≤ j ≤ N. (3) Эти величины используются в качестве искусственных ключей, а также как граничные признаки. Равенство в (3), вообще говоря, исключено. Если же оно тем не менее допускается, алгоритмы можно модифицировать так, чтобы они все-таки работали, хотя нередко при этом их изящество и эффективность отчасти утрачиваются. Обычно сортировку подразделяют на два класса: внутреннюю, когда все записи хранятся в быстрой оперативной памяти, и внешнюю, когда все они там не помещаются. При внутренней сортировке имеются более гибкие возможности для построения структур данных и доступа к ним, внешняя же показывает, как поступать в условиях сильно ограниченного доступа. Достаточно хороший общий алгоритм затрачивает на сортировку N записей время порядка N log N ; при этом требуется около log N ”проходов” по данным. Как мы увидим в п. 5.3.1, это минимальное время. Так, если удвоить число записей, то и время при прочих равных условиях возрастет немногим более чем вдвое. (На самом деле, когда N стремится к ∞, время растет как N (log N )2 , если все ключи различны, так как и размеры ключей увеличиваются с ростом N ; но практически N всегда остается ограниченным.) Упражнения (ПЕРВАЯ ЧАСТЬ) 1. [М20] Докажите, что из законов трихотомии и транзитивности вытекает единственность перестановки p(1), p(2), . . . , p(N ), если сортировка устойчива. 2. [21] Пусть каждая запись R. некоторого файла имеет два ключа: ”большой ключ” Kj и ”малый ключ” kj , причем оба множества ключей линейно упорядочены. Тогда можно обычным способом ввести ”лексикографический порядок” на множестве пар ключей (K, k): (Ki , ki ) < (Kj , kj ), если Ki < Kj или если Ki = Kj и ki < kj . Некто (назовем его мистер A) отсортировал этот файл сначала по большим ключам, получив n групп записей с одинаковыми большими ключами в каждой группе: Kp(1) = · · · = Kp(i1 ) < Kp(i1 +1) = · · · = Kp(i2 ) < · · · < Kp(in−1 +1) = · · · = Kp(in ) , где in = N . Затем каждую из n групп Rp(ij−1 +1) , . . . , Rp(ij ) он отсортировал по малым ключам. Тот же исходный файл взял мистер B и отсортировал его сначала по малым ключам, а потом получившийся файл отсортировал по большим ключам. Взяв тот же исходный файл, мистер C отсортировал его один раз, пользуясь лексикографическим порядком между парами ключей (Kj , kj ). Получилось. ли у всех троих одно и то же? 3. [M25] Пусть на множестве K1 , . . . , KN определено отношение <, для которого закон трихотомии выполняется, а закон транзитивности— нет. Докажите, что и в этом случае возможна устойчивая сортировка записей, т. е. такая, что выполняются условия (1) и (2); на самом деле существуют по крайней мере три расположения записей, удовлетворяющих этим условиям! 4. [15] Мистер Тупица (программист) захотел узнать, находится ли в ячейке A машины MIX число, большее числа из ячейки B, меньшее или же равное ему. Он написал LDA A SUB B а потом проверил, какой результат получился в rA: положительное число, отрицательное или нуль. Какую серьезную ошибку он допустил и как должен был поступить? 5. [17] Напишите MIX-подпрограмму для сравнения ключей, занимающих несколько слов, исходя из следующих условий: Вызов: Состояние при входе: JMP COMPARE rI1 = n; CONTENTS(A + k) = ak , CONTENTS(B + k) = bk при 1 ≤ k ≤ n; предполагается, что n ≥ 1. Состояние при выходе: CI = +1, если (an , . . . , a1 ) > (bn , ..., b1 ); CI = 0, если (an , . . . , a1 ) = (bn , ..., b1 ); CI = −1, если (an , . . . , a1 ) < (bn , ..., b1 ); rX и rI1, возможно, изменились. Здесь отношение (an , . . . , a1 ) < (bn , ..., b1 ) обозначает лексикографическое упорядочение слева направо, т. е. существует индекс j, такой, что ak = bk при n ≥ k > j, но aj < bj . 6. [30] В ячейках A и B содержатся соответственно числа a и b. Покажите, что можно написать MIX-программу, которая бы вычисляла min(a, b) и записывала результат в ячейку C, не пользуясь командами перехода. (Предостережение: поскольку арифметическое переполнение невозможно обнаружить без команд перехода, разумно так построить программу, чтобы переполнение не могло возникнуть ни при каких значениях a и b) 7. [М27] Какова вероятность того, что после сортировки в неубывающем порядке N независимых равномерно распределенных на отрезке [0, 1] случайных величин r-е от начала число окажется ≤ x? Упражнения (ВТОРАЯ ЧАСТЬ) В каждом из этих упражнений поставлена задача, с которой может столкнуться программист. Предложите ”хорошее” решение задачи, предполагая, что имеется сравнительно небольшая оперативная память и около полудюжины лентопротяжных устройств (этого количества достаточно для сортировки). 1. [75] Имеется лента, на которой записан миллион слов данных. Как определить, сколько на этой ленте различных слов? 2. [18] Вообразите себя в роли Управления внутренних доходов Министерства финансов США. Вы получаете миллионы ”информационных” карточек от организаций о том, сколько денег они выплатили различным лицам, и миллионы ”налоговых” карточек от различных лиц об их доходах. Как бы вы стали отыскивать людей, которые сообщили не обо всех своих доходах? 3. [М25](Транспонирование матрицы.) Имеется магнитная лента, содержащая миллион слов, которые представляют собой элементы 1000 × 1000-матрицы, записанные по строкам: a1,1 a1,2 . . . a1,1000 a2,1 . . . a2,1000 . . . a1000,1000 . Ваша задача—получить ленту, на которой элементы этой матрицы были бы записаны по столбцам: a1,1 a2,1 . . . a1000,1 a1,2 . . . a1,2 . . . a1000,2 . . . a1000,1000 (Постарайтесь сделать не более десяти просмотров данных.) 4. [М26] В вашем распоряжении довольно большой файл из N слов. Как бы вы его ”перетасовали” случайным образом? >5. [24] В неком университете работает около 1000 преподавателей и имеется 500 комитетов. Считается, что каждый преподаватель является членом по крайней мере двух комитетов. Вам нужно подготовить с помощью машины удобочитаемые списки членов всех комитетов. Вы располагаете колодой из приблизительно 1500 перфокарт, сложенных произвольным образом и содержащих следующую информацию: Членские карточки: колонка 1—пробел; колонки 2–18—фамилия с последующими пробелами; колонки 19–20—инициалы; колонки 21–23—номер первого Комитета; колонки 24–26—номер второго комитета; . . . ; колонки 78–80— номер двадцатого комитета (если нужно) или пробелы. Комитетские карточки: колонка 1—”*”; колонки 2–77—название комитета; колонки 78–80— номер комитета. Как вы должны действовать? (Опишите свой метод достаточно подробно.) 6. [20] Вы работаете с двумя вычислительными системами, в которых по-разному упорядочены литеры (буквы и цифры). Как заставить первую ЭВМ сортировать файлы с буквенно-цифровой информацией, предназначенные для использования на второй ЭВМ? 7. [18] Имеется довольно большой список людей, родившихся в США, с указанием штата, в котором они родились. Как подсчитать число людей, родившихся в каждом штате? (Предполагается, что ни один человек не указан в списке более одного раза.) 8. [20] Чтобы облегчить внесение изменений в большие программы, написанные на ФОРТРАНе, вы хотите написать программу, выпечатывающую таблицу ”перекрестных ссылок”. Входными данными для нее служит программа на ФОРТРАНе, а в результате получается листинг исходной программы, снабженный указателем всех случаев употребления каждого идентификатора (т. е. имени) в программе. Как написать такую программу? 9. [33] (Сортировка каталожных карточек.) Способы составления алфавитных каталогов в разных библиотеках несколько отличаются друг от друга. В следующем ”алфавитном” списке содержатся рекомендации, взятые из правил регистрации и хранения каталожных карточек Американской библиотечной ассоциации (Чикаго, 1942): Текст карточки R. Accademia nazionale dei Lincei, Rome 1812; ein historischer roman. Bibliothèque d’histoire révolutionnaire. Замечания В названиях иностранных (кроме британских) учреждений слово ”royalty” (королевский) игнорируется Achtzehnhundert zwölf Bibliothèque des curiosités. Во французском тексте апостроф рассматривается как пробел Надстрочные знаки игнорируются Brown, Mrs. J. Crosby Указание положения (Mrs.) игнорируется Brown, John Фамилии с датами следуют за фамилиями без дат... Brown, John, mathematician . . . которые упорядочиваются по Brown, John, of Boston описательным словам Brown, John, 1715–1766 Одинаковые фамилии упорядочиваются по датам рождения Работы ”о нем” идут после его работ BROWN, JOHN, 1715–1766 Brown, John, d. 1811 Brown, Dr. John, 1810–1882 Иногда год рождения определяется приблизительно Указание положения (Dr.) игнорируется Brown-Williams, Reginald Makepeace Дефис рассматривается как пробел Brown America. Названия книг идут после составных фамилий Brown & Dallison’s Nevada directory. & в английском тексте превращается в ”and” Brownjohn, Alan Den’, Vladimir Éduardovich, 1867– Апостроф в именах игнорируется The den. Артикль в начале текста игнорируется Den lieben süssen mädeln. Dix, Morgan, 1827–1908 . . . если существительное стоит в именительном падеже Фамилии идут раньше других слов 1812 ouverture. Dix-huit cent douze Le XIXe siècle français. Dix-neuvième The 1847 issue of U. S. stamps. Eighteen forty-seven 1812 overture. Eighteen twelve I am a mathematician, (by Norbert Weiner) IBM journal of research and development. ha-I ha-eh.ad. Аббревиатуры рассматриваются как ряд однобуквенных слов Артикль в начале текста игнорируется Ia; a love story. Знаки препинания в названиях игнорируются International Business Machines Corporation al-Khuwārizmı̄, Muh.ammad ibn Mūsā, fl. 813–846 Начальное ”аl-” в арабских именах игнорируется Labour; a magazine for all workers. Заменяется на ”Labor” Labor research association Labour, see Labor Ссылка на другую карточку в картотеке McCall’s cookbook Апостроф в английском тексте игнорируется McCarthy, John, 1927– Mc = Mac Machine-independent computer programming. Дефис рассматривается как пробел MacMahon, Maj. Percy Alexander, 1854–1929 Указание положения (Maj) игнорируется