2.7. БАЛАНСИРОВКА

В обоих наших примерах на технику "разделяй и властвуй" задача разбивалась на подзадачи равных размеров. Это не было случайностью. Поддержание равновесия — основной руководящий принцип при разработке хорошего алгоритма. Для иллюстрации этого принципа мы приведем пример из сортировки и сопоставим эффекты от разбиения задачи на подзадачи неравных размеров и на подзадачи равных размеров. Из этого примера не следует заключать, что "разделяй и властвуй" — единственная техника, в которой полезна балансировка. В гл. 4 приводится несколько примеров, в которых эффективные алгоритмы получаются в результате балансировки размеров поддеревьев или весов двух операций.

Рассмотрим задачу расположения целых чисел в порядке неубывания. По-видимому, простейший способ сделать это — найти наименьший элемент, исследуя всю последовательность и затем меняя местами наименьший элемент с первым. Процесс повторяется на остальных элементах, и это повторение приводит к тому, что второй наименьший элемент оказывается на втором месте. Повторение процесса на остальных элементах сортирует всю последовательность.

Этот алгоритм приводит к рекуррентным уравнениям

для числа сравнений, произведенных между сортируемыми элементами. Решением для (2.7) служит что составляет

Хотя этот алгоритм можно считать рекурсивным применением приема "разделяй и властвуй" с разбиением задачи на неравные части, он не эффективен для больших Для разработки асимптотически эффективного алгоритма сортировки надо позаботиться о сбалансированности. Вместо того чтобы разбивать задачу размера на две подзадачи, одна из которых имеет размер 1, а другая — размер надо разбить ее на две подзадачи с размерами примерно Это выполняется методом, известным как сортировка слиянием.

Рассмотрим последовательность целых чисел Снова предположим для простоты, что есть степень числа 2. Один из способов упорядочить эту последовательность — разбить ее на две подпоследовательности упорядочить каждую из них и затем слить их. Под "слиянием" мы понимаем объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.

Алгоритм 2.4. Сортировка слиянием

Вход. Последовательность чисел где степень числа 2.

Выход. Последовательность являющаяся перестановкой входа и удовлетворяющая неравенствам

Метод. Применим процедуру входом которой служат две упорядоченные последовательности а выходом — последовательность элементов из расположенных в порядке неубывания. Поскольку сами упорядочены, СЛИЯНИЕ требует сравнений не больше, чем сумма длин без единицы. Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в и в последующем удалении выбранного элемента. В случае совпадения можно отдавать предпочтение последовательности

Рис. 2.14. Сортировка слиянием.

Кроме того, применяется процедура сортирующая подпоследовательность в предположении, что она имеет длину 2 для некоторого

Для сортировки данной последовательности вызывается процедура

Подсчет числа сравнений в алгоритме 2.4 приводит к рекуррентным уравнениям

решением которых по теореме 2.1 является Для больших сбалансированность размеров подзадач дала значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры затрачиваемое не только на сравнения, также есть