ИНСТИТУТ ТОЧНОЙ МЕХАНИКИ И ОПТИКИ
                 (САНКТ-ПЕТЕРБУРГ)
         Кафедра прикладной математики



         ОПИСАНИЯ КОМБИНАТОРНЫХ АЛГОРИТМОВ

         для выполнения лабораторных работ
         по курсу   "Комбинаторные алгоритмы"



         составил доц. Кукушкин Б.А.
                1994 - 1995 г.


                СОДЕРЖАНИЕ

ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ  .............................4

1. Методы вставки. Алгоритм простых вставок.   .............4
1.1. Бинарные вставки    ...................................5
1.2. Двухпутевые вставки    ................................6
1.3. Вставки одновременно нескольких элементов. ............6
1.4. Вставки с убывающим шагом (метод Шелла)   .............7
1.5. Вставки в связанный список                .............9
1.6. Вставки в несколько связанных списков     ............10

2. Обменная сортировка  ...................................12
2.1. Метод пузырька     ...................................12
2.2. Модификация метода  пузырька   .......................13
2.3. Быстрая сортировка.        ...........................14
2.4. Обменная поразрядная сортировка ......................17
2.5. Параллельная сортировка Бэтчера ......................20

3. Сортировка посредством выбора  .........................24
3.1. Использование связанного списка для хранения
     информации о промежуточных максимумах. ...............24
3.2. Пирамидальная сортировка.   ..........................26

4. Сортировка посредством слияния    ......................31
4.1. Естественное двухпутевое слияние .....................31
4.2. Простое двухпутевое слияние. .........................34
4.3. Слияние связанных списков  ...........................36

5. Распределяющая сортировка  .............................38



ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА    ..............................42

6. Последовательный поиск    ..............................42
6.1. Последовательный поиск в неупорядоченном файле........42
6.2. Последовательный поиск по связанному списку   ........43
6.3. Последовательный поиск в упорядоченном файле     .....44
6.4. Бинарный поиск в упорядоченном файле.  ...............44
6.5. Однородный бинарный поиск         ....................45
6.6. Интерполяционный поиск            ....................46

7. Поиск по бинарным деревьям       .......................47
7.1. Поиск по бинарному дереву.     .......................47
7.2. Удаление из бинарного дерева   .......................48
7.3. Построение оптимальных бинарных деревьев поиска ......48
7.4. Цифровой поиск по дереву     .........................52
7.5. Цифровой поиск для длинных ключей, хранимых в
     текстовом массиве (Патриция)   .......................52

8. ЛАБОРАТОРНЫЕ ЗАДАНИЯ     ...............................57

8.1. Сортировка     .......................................57
8.2. Поиск    .............................................59



   Обозначения, использованные в данном пособии.

log    логарифм по основанию 2
+   +
| А | наименьшее целое значение, большее или равное А

| А | наибольшее целое значение, меньшее или равное А
+   +

 ЛИТЕРАТУРА

 1. Д.Кнут,Искусство программирования, М.:Мир,1978.

 2. Рейнгольд, Нивергельт, Део, Комбинаторные алгоритмы.
    Теория и практика, М.:Мир, 1982.