От издателей русского перевода 1
О книге "Искусство программирования" 2
От редактора перевода 4
ПРЕДИСЛОВИЕ 5
Предисловие ко второму изданию 6
ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 8
*5.1. КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК 12
*5.1.1. Инверсии 12
УПРАЖНЕНИЯ 18
*5.1.2. Перестановки мультимножества 23
УПРАЖНЕНИЯ 32
*5.1.3. Серии 36
УПРАЖНЕНИЯ 46
*5.1.4. Диаграммы и инволюции 49
УПРАЖНЕНИЯ 66
5.2. ВНУТРЕННЯЯ СОРТИРОВКА 75
УПРАЖНЕНИЯ 81
5.2.1. Сортировка путем вставок 82
Бинарные и двухпутевые вставки. 84
* Анализ метода Шелла. 88
Следствие. 91
Алгоритм L (Метод вставки в список). 99
Сортировка с вычислением адреса. 101
УПРАЖНЕНИЯ 105
5.2.2. Обменная сортировка 109
Метод пузырька. 109
Анализ метода пузырька. 111
Модификация метода пузырька. 113
Параллельная сортировка Бэтчера. 114
Быстрая сортировка. 117
Алгоритм Q (Быстрая сортировка). 119
Программа Q (Обменная сортировка с разделением). 121
Анализ метода быстрой сортировки. 122
Обменная поразрядная сортировка. 127
* Асимптотические методы. 133
УПРАЖНЕНИЯ 138
5.2.3. Сортировка посредством выбора 143
Усовершенствования простого выбора. 145
Выбор из дерева. 146
Пирамидальная сортировка. 150
Программа Н (Пирамидальная сортировка). 151
Наибольший из включенных первым исключается. 154
Связанное представление приоритетных очередей. 155
Сравнение методов работы с приоритетными очередями. 156
*Анализ пирамидальной сортировки. 158
УПРАЖНЕНИЯ 161
5.2.4. Сортировка методом слияния 164
УПРАЖНЕНИЯ 173
5.2.5. Сортировка методом распределения 175
УПРАЖНЕНИЯ 184
5.3. ОПТИМАЛЬНАЯ СОРТИРОВКА 187
5.3.1. Сортировка с минимальным числом сравнений 187
Оптимизация в наихудшем случае. 189
*Более глубокий анализ. 194
Среднее число сравнений. 199
УПРАЖНЕНИЯ 201
*5.3.2. Слияние с минимальным числом сравнений 204
Определение нижних оценок. 206
Верхние оценки. 210
Алгоритм Н (Бинарное слияние). 211
УПРАЖНЕНИЯ 212
*5.3.3. Выбор с минимальным числом сравнений 215
Среднее число. 223
УПРАЖНЕНИЯ 225
*5.3.4. Сети сортировки 228
Сети с минимальным числом сравнений. 234
Сети с минимальным временем. 236
Битонная сортировка. 239
УПРАЖНЕНИЯ (часть 1) 243
УПРАЖНЕНИЯ (часть 2) 253
5.4. ВНЕШНЯЯ СОРТИРОВКА 257
УПРАЖНЕНИЯ 261
5.4.1. Многопутевое слияние и выбор с замещением 261
Дерево "проигравших” 262
Получение начальных серий посредством выбора с замещением. 264
*Преобразование серий с задержкой. 268
.Натуральный выбор. 269
УПРАЖНЕНИЯ 272
*5.4.2. Многофазное слияние 277
Более детальный анализ. 283
А как обстоит дело с временем перемотки? 289
Расщепление лент. 291
УПРАЖНЕНИЯ 295
*5.4.3. Каскадное слияние 298
Начальное распределение серий. 299
Анализ каскадного слияния. 304
Модификация каскадной сортировки. 308
УПРАЖНЕНИЯ 308
*5.4.4. Чтение ленты в обратном направлении 310
Обратное чтение в многофазном слиянии. 311
Оптимальные схемы слияния. 313
УПРАЖНЕНИЯ (часть 1) 319
УПРАЖНЕНИЯ (часть 2) 321
*5.4.5. Осциллирующая сортировка 323
Алгоритм В (Осциллирующая сортировка с “перекрестным” распределением). 324
Прямое чтение. 326
УПРАЖНЕНИЯ 329
*5.4.6. Практическая реализация слияния на лентах 329
Как работает НМЛ. 329
Сравнительный анализ схем слияния. 336
Пример 1. Сбалансированное слияние с прямым чтением. 337
Пример 2. Многофазное слияние с прямым чтением. 337
Пример 3. Каскадное слияние с прямым чтением. 342
Пример 4. Многофазное слияние с расщеплением лент. 342
Пример 5. Каскадное слияние с совмещением перемоток. 343
Пример 6. Сбалансированное слияние с обратным чтением. 343
Пример 7. Многофазное слияние с обратным чтением. 344
Пример 8. Каскадное слияние с обратным чтением. 344
Пример 9. Осциллирующая сортировка с обратным чтением. 344
Пример 10. Осциллирующая сортировка с прямым чтением.345
Оценка времени выполнения. 345
Формулы для десяти примеров. 349
Пример 1. Сбалансированное слияние с прямым чтением. 349
Пример 2. Многофазное слияние с прямым чтением. 349
Пример 3. Каскадное слияние с прямым чтением. 349
Пример 4. Многофазное слияние с расщеплением лент. 349
Пример 5. Каскадное слияние с совмещением перемоток. 349
Пример 6. Сбалансированное слияние с обратным чтением. 350
Пример 7. Многофазное слияние с обратным чтением. 350
Пример 8. Каскадное слияние с обратным чтением. 350
Пример 9. Осциллирующая сортировка с обратным чтением. 350
Пример 10. Осциллирующая сортировка с прямым чтением. 350
Несколько дополнительных замечаний. 351
Генераторы сортировки. 355
*Слияние с меньшим числом буферов. 356
УПРАЖНЕНИЯ 358
*5.4.7. Внешняя поразрядная сортировка 359
Имеет ли поразрядная сортировка преимущество перед слиянием. 364
УПРАЖНЕНИЯ 364
*5.4.8. Сортировка с двумя лентами 365
Применение быстрой сортировки. 366
Поразрядная сортировка. 368
Имитация дополнительных лент. 369
Одноленточная сортировка. 370
УПРАЖНЕНИЯ 373
*5.4.9. Диски и барабаны 374
Способы сокращения времени ожидания. 376
Барабаны: случай, когда поиск не нужен. 376
Влияние времени поиска. 379
*Подробности об оптимальных деревьях. 383
*Еще один способ распределения буферов. 385
Использование сцепления. 386
Пересмотренный вариант прогнозирования. 387
Использование нескольких дисков. 388
Рандомизированное разделение. 389
Поможет ли сортировка ключей? 392
УПРАЖНЕНИЯ 394
5.5. РЕЗЮМЕ. ИСТОРИЯ И БИБЛИОГРАФИЯ 399
Ранние разработки. 403
Последние достижения. 409
УПРАЖНЕНИЯ 410
ГЛАВА 5
СОРТИРОВКА 412
УПРАЖНЕНИЯ (часть 1) 416
УПРАЖНЕНИЯ (часть 2) 417
ГЛАВА 6
ПОИСК 422
6.1. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК 426
Частота обращений. 429
"Самоорганизующийся" файл. 432
Поиск на ленте с неравными записями. 433
УПРАЖНЕНИЯ 435
6.2. ПОИСК ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ 439
6.2.1. Поиск в упорядоченной таблице 439
Бинарный поиск. 439
Алгоритм В (Бинарный поиск (Binary search)). 440
Программа В (Бинарный поиск). 441
Дальнейший анализ бинарного поиска. 443
*Поиск Фибоначчи. 447
Интерполяционный поиск. 449
История и библиография. 450
УПРАЖНЕНИЯ 453
6.2.2. Поиск по бинарному дереву 456
Удаление. 462
Алгоритм D (Удаление из дерева (Tree deletion)). 462
Частота обращений. 465
Оптимальные бинарные деревья поиска. 466
Оптимальные деревья и энтропия. 473
* Алгоритм Гарсия-Воча.477
История и библиография. 484
УПРАЖНЕНИЯ 485
6.2.3. Сбалансированные деревья 489
Анализ вставки в сбалансированное дерево. 498
*Удаление, конкатенация и другие операции. 504
Альтернативы АVL-деревьям. 507
УПРАЖНЕНИЯ 510
6.2.4. Сильноветвящиеся деревья 513
Усовершенствования и изменения. 518
УПРАЖНЕНИЯ 522
6.3. ЦИФРОВОЙ ПОИСК 524
Бинарный цифровой поиск. 528
Анализ алгоритмов. 533
УПРАЖНЕНИЯ 539
6.4. ХЕШИРОВАНИЕ 546
Разрешение коллизий методом "цепочек” 554
Разрешение коллизий методом открытой адресации. 559
Алгоритм L (Линейное исследование и вставка). 559
Программа L (Линейное исследование и вставка). 560
Алгоритм D (Открытая адресация с двойным хешированием). 562
Изменение Брента. 565
Удаления. 567
* Анализ алгоритмов. 568
* Анализ оптимальности. 573
Внешний поиск. 575
История. 581
УПРАЖНЕНИЯ 583
6.5. ВЫБОРКА ПО ВТОРИЧНЫМ КЛЮЧАМ 594
Инвертированные файлы. 596
Геометрические данные. 598
Составные атрибуты. 602
Комбинаторное хеширование. 609
Обобщенные лучи (tries). 612
*Сбалансированные схемы. 612
Краткая история и библиография. 614
УПРАЖНЕНИЯ 615
ОТВЕТЫ К УПРАЖНЕНИЯМ 620
РАЗДЕЛ 5 620
РАЗДЕЛ 5.1.1 628
РАЗДЕЛ 5.1.2 634
РАЗДЕЛ 5.1.3 639
РАЗДЕЛ 5.1.4 644
РАЗДЕЛ 5.2 653
РАЗДЕЛ 5.2.1 656
РАЗДЕЛ 5.2.2 666
РАЗДЕЛ 5.2.3 678
РАЗДЕЛ 5.2.4 685
РАЗДЕЛ 5.2.5 689
РАЗДЕЛ 5.3.1 692
РАЗДЕЛ 5.3.2 698
РАЗДЕЛ 5.3.3 701
РАЗДЕЛ 5.3.4 706
РАЗДЕЛ 5.4 717
РАЗДЕЛ 5.4.1 717
РАЗДЕЛ 5.4.2 721
РАЗДЕЛ 5.4.3 725
РАЗДЕЛ 5.4.4 727
РАЗДЕЛ 5.4.5 732
РАЗДЕЛ 5.4.6 733
РАЗДЕЛ 5.4.8 736
РАЗДЕЛ 5.5 743
РАЗДЕЛ 6.1 744
РАЗДЕЛ 6.2.1 747
РАЗДЕЛ 6.2.2 750
РАЗДЕЛ 6.2.3 756
РАЗДЕЛ 6.2.4 761
РАЗДЕЛ б.3 763
РАЗДЕЛ 6.4 770
РАЗДЕЛ 6.5 786
ПРИЛОЖЕНИЕ А
ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ 791
ПРИЛОЖЕНИЕ Б
ОСНОВНЫЕ ОБОЗНАЧЕНИЯ 795
Д.Э. Кнут "Искусство программирования" том 3 "Сортировка и поиск"