- •2.2. Методы разработки алгоритмов
- •2.2.1. Метод декомпозиции
- •2.2.2. Динамическое программирование
- •2.2.3. Поиск с возвратом
- •2.2.4. Метод ветвей и границ
- •2.2.5. Метод альфа-бета отсечения
- •2.3. Алгоритмы поиска
- •2.3.1. Поиск в линейных структурах
- •2.3.1.2. Бинарный поиск
- •2.3.2. Хеширование данных
- •2.3.2.1. Функция хеширования
- •2.3.2.2. Открытое хеширование
- •2.3.2.3. Закрытое хеширование
- •2.3.2.4. Реструктуризация хеш-таблиц
- •2.3.4. Поиск по вторичным ключам
- •2.3.3.1. Инвертированные индексы
- •2.3.3.2. Битовые карты
- •2.3.4.1. Упорядоченные деревья поиска
- •2.3.4.2. Случайные деревья поиска
- •2.3.4.3. Оптимальные деревья поиска
- •2.3.5. Поиск в тексте
- •2.3.5.1. Прямой поиск
- •2.3.5.3. Алгоритм Боуера и Мура
- •2.4.1. Основные виды сжатия
- •2.4.3. Кодовые деревья
- •2.5. Алгоритмы сортировки
- •2.5.1. Основные виды сортировки
- •2.5.2.1. Сортировка подсчетом
- •2.5.2.2. Сортировка простым включением
- •2.5.2.3. Сортировка методом Шелла
- •2.5.2.5. Древесная сортировка
- •2.5.2.6. Сортировка методом пузырька
- •2.5.2.7. Быстрая сортировка (Хоара)
- •2.5.2.8. Сортировка слиянием
- •2.5.2.9. Сортировка распределением
- •2.5.3. Алгоритмы внешней сортировки
- •2.6. Алгоритмы на графах 2.6.1. Алгоритм определения циклов
- •2.6.2. Алгоритмы обхода графа
- •2.6.2.1. Поиск в глубину
- •2.6.3. Нахождение кратчайшего пути
- •2.6.3.1. Алгоритм Дейкстры
- •2.6.3.2. Алгоритм Флойда
- •2.6.3.3. Переборные алгоритмы
- •2.6.4.1. Алгоритм Прима
- •2.6.4.2. Алгоритм Крускала
- •190000, Санкт-Петербург, ул. Б. Морская, 67
2.5.3. Алгоритмы внешней сортировки
Как уже говорилось выше, внешняя сортировка – это упорядочивание данных, которые хранятся на внешнем устройстве с медленным доступом (диск, лента и т. д.), и прежде всего надо уменьшить число обращений к этому устройству, т. е. число проходов через файл.
Обычно данные, хранящиеся на внешних устройствах, имеют большой объем, что не позволяет их целиком переместить в оперативную память, отсортировать с использованием одного из алгоритмов внутренней сортировки, а затем вернуть их на внешнее устройство. В этом случае осуществлялось бы минимальное количество проходов через файл: однократное чтение и однократная запись данных. Однако на практике приходится осуществлять чтение, обработку и запись данных в файл по блокам, размер которых зависит от операционной системы и имеющегося объема оперативной памяти, что приводит к увеличению числа проходов через файл и заметному снижению скорости сортировки.
Применение большинства алгоритмов внутренней сортировки для сортировки файлов требует порядка O(n) проходов. Однако, если несколько модифицировать алгоритм сортировки слиянием (см. п. 2.5.2.8), то можно произвести сортировку, осуществляя порядка O(log n) проходов.
Основное отличие сортировки слиянием для файлов, заключается в следующем. Вся сортируемая последовательность данных разбивается на два файла f1 и f2. Желательно, чтобы количество записей в этих файлах было поровну. Как и в алгоритме внутренней сортировки, считаем, что любой файл состоит из участков длиной 1. Затем можно объединить участки длины 1 и распределить их по файлам g1 и g2 в виде участков длины 2. После этого делаем f1 и f2 пустыми и объединяем g1 и g2 в f1 и f2, которые затем можно организовать в виде участков длины 4 и т. д.
После выполнения i подобного рода проходов получатся два файла, состоящие из участков длины 2i. Если 2i ≥ n, тогда один из этих двух файлов будет пустым, а другой будет содержать единственный участок длиной n, т. е. будет отсортирован. Так как 2i ≥ n при i ≥ log n, то не-152
трудно заметить, что в этом случае будет достаточно порядка O(log n) проходов по данным.
Пример внешней сортировки слиянием приведен на рис. 49.
Исходные файлы Участки длиной 2
1 28 1 |
3 |
| 93 | 10 | 54 | 65 | |
30 |
90 | |
|
|
|
|
|
1 31 1 |
5 |
| 96 | 40 | 85 | 9 | |
39 |
|
|
|
Участки длиной 4 |
|
|
|
5 |
1 28 | 31 | 9 I 54 | |
65 |
85 1 |
1 28 |
31 |
I 93 | 96 | 54 | 85 | 30 | 39 I |
| ||
1 3 |
5 |
| 10 | 40 | 9 | 65 | 90 | |
Участки длиной 8 | ||
1 3 |
5 |
| 10 | 28 | 31 | 40 | 93 | 96 | |
| 10 | 40 | 93 | 96 | 30 | 39 | 90 | | 9 | 30 | 39 | 54 | 65 | 85 | 90 |
Участки длиной 16
| 3 | 5 | 9 | 10 | 28 | 30 | 31 | 39 | 40 | 54 | 65 | 85 | 90 | 93 | 96 | |
Рис. 49. Внешняя сортировка слиянием
При такой сортировке не требуется, чтобы отдельный участок полностью находился в оперативной памяти (при большой длине он может не поместиться в буфер). Участок считывается и записывается последовательно запись за записью. Именно такой подход заставляет использовать два входных файла. В противном случае можно было бы читать по два участка из одного файла одновременно.