Во втором издании третьего тома содержится полный обзор классических алгоритмов сортировки и поиска. Представленная в нем информация дополняет приведенное в первом томе обсуждение структур данных. Автор рассматривает принципы построения больших и малых баз данных, а также внутренней и внешней памяти. В книге приведена подборка тщательно проверенных компьютерных алгоритмов и представлен анализ их эффективности. Кроме того, специальный раздел посвящен методам оптимальной сортировки и описанию новой теории перестановки и универсального хеширования
Содержание
Глава 5. Сортировка
5.1. Комбинаторные свойства перестановок
5.1.1. Инверсии
5.1.2. Перестановки мультимножества
5.1.3. Серии
5.1.4. Диаграммы и инволюции
5.2. Внутренняя сортировка
5.2.1. Сортировка путем вставок
5.2.2. Обменная сортировка
5.2.3. Сортировка посредством выбора
5.2.4. Сортировка методом слияния
5.2.5. Сортировка методом распределения
5.3. Оптимальная сортировка
5.3.1. Сортировка с минимальным числом сравнений
5.3.2. Слияние с минимальным числом сравнений
5.3.3. Выбор с минимальным числом сравнений
5.3.4. Сети сортировки
5.4. Внешняя сортировка
5.4.1. Многопутевое слияние и выбор с замещением
5.4.2. Многофазное слияние
5.4.3. Каскадное слияние
5.4.4. Чтение ленты в обратном направлении
5.4.5. Осциллирующая сортировка
5.4.6. Практическая реализация слияния на лентах
5.4.7. Внешняя поразрядная сортировка
5.4.8. Сортировка с двумя лентами
5.4.9. Диски и барабаны
5.5. Резюме. История и библиография
Глава 6. Поиск
6.1. Последовательный поиск
6.2. Поиск путем сравнения ключей
6.2.1. Поиск в упорядоченной таблице
6.2.2. Поиск по бинарному дереву
6.2.3. Сбалансированные деревья
6.2.4. Сильноветвящиеся деревья
6.3. Цифровой поиск
6.4. Хеширование
6.5. Выборка по вторичным ключам
Ответы к упражнениям
Приложение А. Таблицы значений некоторых констант
A.1. Основные константы (десятичные)
А.2. Основные константы (восьмеричные)
А.З. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи
Для профессионала эта книга может служить настольным справочником, для преподавателя - пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов - отличным учебником. Каждый может найти в ней именно тот материал, который касается интересующей его темы, и изложенный именно с тем уровне сложности и строгости, который требуется читателю.
Этот выпуск представляет собой продолжение главы о комбинаторных алгоритмах, которая будет включена в четвертый том Искусства программирования. Поскольку часть этого тома составит большая глава о комбинаторном поиске, то этот выпуск начинается с рассмотрения генерации всех возможных объектов. Особое внимание уделяется генерации всех n-кортежей, которые расширяют эти идеи для всех перестановок. Такие алгоритмы дают естественную мотивацию, с помощью которой вводятся и развиваются многие ключевые идеи комбинаторной математики.
