- •Очереди с приоритетами. Методы их реализации
- •Реализация очереди с приоритетами частично упорядоченными деревьями
- •Деревья двоичного поиска
- •Нагруженные деревья
- •Реализация множеств посредством сбалансированных деревьев
- •Множества с операторами merge и find
- •Задача наибольшей общей подпоследовательности
- •Сбалансированные и несбалансированные деревья поиска
- •Внешняя сортировка. Основные характеристики сортировок методом слияний
- •Алгоритм прямого слияния.
- •Алгоритм естественного слияния.
- •Сбалансированное многопутевое слияние
- •Многофазная сортировка.
Алгоритм прямого слияния.
На первом шаге упорядоченные отрезки имеют длину, равную единице, т.е. состоят из одного элемента.
Затем они объединяются и в случае двухпутевого слияния вновь сформированные отрезки будут состоять из двух элементов, а в случае многопутевого – из N элементов.
Предположим, что имеется последовательный файл F0, состоящий из записей a1, a2, ..., an.
Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки.
Для сортировки используются два вспомогательных файла F1 и F2 (размер каждого из них будет n/2).
Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла F0 в файлы F1 и F2, а затем слияние файлов F1 и F2 в файл F0.
На первом шаге для распределения последовательно читается файл F0, и
записи a1, a3, ..., an-1 пишутся в файл F1,
а записи a2, a4, ..., an - в файл F2 (начальное распределение).
Начальное слияние производится над парами (a1, a2), (a3, a4), ..., (an-1, an), и результат записывается в файл F0.
На втором шаге снова последовательно читается файл F0,
и в файл F1 записываются последовательные пары с нечетными номерами,
а в файл F2 - с четными.
При слиянии образуются и пишутся в файл F0 упорядоченные четверки записей.
И так далее.
Перед выполнением последнего шага файл F0 будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении
первая из них попадет в файл F1,
а вторая - в файл F2.
После слияния файл F0 будет содержать полностью упорядоченную последовательность записей.
Сортировка прямым слиянием заканчивается, если:
после фазы слияния длина серии не меньше количества элементов в файле;
на фазе слияния осталась ровно одна серия;
второй по счету вспомогательный файл для однофазной сортировки после распределения серий остался пустым.
Алгоритм естественного слияния.
Всегда сливаются две самые длинные из возможных серий, т.е. объединяются серии максимальной, а не заранее фиксированной длины.
Признаком конца серии в этом случае является результат сравнения двух соседних элементов, если они упорядочены, то серия закончилась.
В каждом проходе число серий уменьшается в N раз (если количество серий во вспомогательных файлах одинаково), а общее число пересылок не более, чем n ∗ [log n].
Ожидаемое число сравнений значительно больше, поскольку кроме сравнений, необходимых для слияния, требуются дополнительные сравнения для определения конца серии.
Так же как и прямое слияние, сортировка естественным слиянием может быть
двухпутевой или многопутевой,
двухфазной или однофазной.
При распределении распознается
первая серия записей и переписывается в файл F1,
вторая - в файл F2 и т.д.
При слиянии
первая серия записей файла F1 сливается с первой серией файла F2,
вторая серия F1 со второй серией F2 и т.д.
Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла F0.
Процесс завершается, когда в файле F0 остается только одна серия.
Пусть исходный файл состоит из элементов:
F0: 1 3 14 6 8 9 2 4 5 8 2 3 1 16
Тогда двухпутевое двухфазное естественное слияние будет проходить следующим образом:
Проход |
Распределение |
Слияние |
1 |
F1: 1 3 14 ‘ 2 4 5 8 ‘ 1 16 F2: 6 8 9 ‘ 2 3 |
F0: 1 3 6 8 9 14 2 2 3 4 5 8 1 16 |
2 |
F1: 1 3 6 8 9 14 ‘ 1 16 F2: 2 2 3 4 5 8 ‘ |
F0: 1 2 2 3 3 4 5 6 8 8 9 14 1 16 |
3 |
F1: 1 2 2 3 3 4 5 6 8 8 9 14 F2: 1 16 |
F0: 1 1 2 2 3 3 4 5 6 8 8 9 14 16 |
Для упорядочивания данных в сортировке прямым слиянием при тех же самых условиях потребовалось бы 4 прохода, поскольку длина серии на 4-ом проходе составляла бы 16 элементов, а в исходном файле содержится 14 элементов.