Третий том известной монографии одного из крупнейших американских специалистов по программированию Д. Кнута (первый том вышел в издательстве «Мир» в 1976 г., второй—в 1977 г.) состоит из двух частей: «Сортировка» и «Поиск». В них подробно исследуются различные алгоритмы внутренней и внешней сортировки, изучаются методы поиска информации в таблицах на основе сравнения или преобразования ключей, даются оценки эффективности предлагаемых алгоритмов. Книга снабжена большим количеством задач и примеров разной степени трудности, существенно дополняющих основной текст.
От других руководств по программированию книга выгодно отличается строгостью изложения и широким применением математического аппарата. Вместе с тем она доступна студентам первого курса: Знакомство с двумя первыми томами Желательно, но необязательно. Каждый, кто хочет научиться квалифицированно программировать, найдет в ней много полезного.
Рассчитана на широкий круг программистов.
ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА
Д. Э. Кнут хорошо знаком советскому читателю по переводам двух первых томов его обширной монографии "Искусство программирования для ЭВМ" и не нуждается в аттестации. Настоящая книга представляет собой третий • том и посвящена алгоритмам сортировки и поиска информации.
Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Написано немало отчетов, статей, монографий. И даже в этих условиях книга Д. Кнута стала событием. По существу это энциклопедия, в которой можно найти любую справку, касающуюся алгоритмов, методов их оценок, истории вопроса и нерешенных проблем.
Нет нужды говорить о важности самой области. Практически сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому, как справедливо отмечает автор, книга адресована не только системным программистам, занимающимся разработкой программ сортировки и поиска информации. Можно сказать, что достаточно^ четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства программирования.
Кроме теоретической и практической ценности, книга имеет большое методическое значение. Многие авторы и преподаватели смогут извлечь из нее новые и полезные сведения не только по существу рассматриваемых вопросов, но и по способу их изложения. Автору мастерски удается "расслоить" весь материал таким образом, что книгу можно использовать практически на любом уровне знакомства с предметом и при различной общей математической подготовленности читателя.
Перевод выполнен по изданию 1973 г. (первая редакция) с внесением многих (около 700) исправлений и добавлений, лю-оезно предоставленных автором. . Разделы с 5.1 по 5.3.2 переведены Н. И. Вьюковой; разделы с 5.3.3 по 5.5 и предисловие — А. ь. Ходулевым; главу 6 перевел В. А. Галатенко.
Ю. М. Банковский В., С. Штаркман
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ,,,,.*<,,.......... 5
Предисловие ............:...........<..» 6
Замечания об упражнениях..................... 9
Глава 5 • \ Сортировка........ . ,...... 13
*5.1. Комбинаторные свойства перестановок .... 24
«5.1.1. Инверсии .............. 24
•5.1.2. Перестановки мультимножества .... 36
*5.1.3. Отрезки............... 50
*5.1.4. Табло и инволюции.......... 65
5.2. Внутренняя сортировка ........... 93
5.2.1. Сортировка вставками ........ «101
5.2.2. Обменная сортировка......... 130
5.2.3. Сортировка посредством выбора ... • 169
5.2.4. Сортировка слиянием........ 193
5.2.5. Распределяющая сортировка ..... 205
5.3. Оптимальная сортировка.......... 218
5.3.1. Сортировка с минимальным числом сравнений ................ 219
*5.3.2. Слияние с минимальным числом сравнений ................. 238
*5.3.3. Выбор с минимальным числом сравнений 251
5.3.4. Сети сортировки........... 265
5.4. Внешняя сортировка............. 295
5.4.1. Многопутевое слияние и выбор с заме-
• . щением............... 300
5.4.2. Многофазное слияние ........ 318
5.4.3. Каскадное слияние ......... 342
5.4.4. Чтение ленты в обратном направлении 355
5.4.5. Осциллирующая сортировка..... 370
5.4.6. Практические аспекты слияния на лен- *
тах................. 378
*5.4.7. Внешняя поразрядная сортировка . * 410
*5.4.8. Сортировка с двумя лентами ..... 417
5.4.9. Диски и барабаны.......... 428
5.5. Резюме. История и библиография ...... 451
Глава 6 | ПОИСК.................... 464
6.1. Последовательный поиск .......... 470
6.2. Поиск посредством сравнения ключей ..... 483
6.2.1. Поиск в упорядоченной таблице . . , 483
6.2.2. Поиск по бинарному дереву < . , , , -502
6.2.3. Сбалансированные деревья ...... 536
6.2.4. Сильно ветвящиеся деревья ...... 561
843
6.3. Цифровой поиск ............... . 672
6.4. Хеширование.........;....• ... 601
'6.5. Выборка по вторичным ключам....., . 651
Ответы к упражнениям ' , ,,............,...'... 676
Приложение А. Таблицы числовых величин.......-...... 812
Приложение .В. Указатель обозначений ,.............. 816
Приложение С. Система команд MIX .,.....'.......... 821
Именной'указатель' •,'.,,..,,,,.,,..,.,.....,. 824
Предметный указатель ........,.....,,,....... 831
Глоссарий1 \ .-.'.........,,,;'.•..,,......., 841
Цена: 300руб.
