Алгоритм 6. Сортировка последовательности чисел слиянием

{

size1=size>>1; // Уменьшение размера массива вдвое

in_min1=in_min; in_max2=in_max; // Указатели на крайние элементы двух

in_max1=in_max-size1; in_min2=in_min1+size1; // новых массивов, составляющих исходный

value1=Max_Min(array, size1, in_min1, in_max1); h4

value2=Max_Min(array, size1, in_min2, in_max2); h5

if (value1.max < value2.max) value.max=value2.max; 32// Вместо этих операторов для массива

else value.max=value1.max; // int можно использовать библиотечные

if (value1.min < value2.min) value.min=value1.min; 33//функции max и min языка C++, что

else value.min=value2.min; // делает программу более изящной

return value;

}

} // Конец Max_Min

Вместо предпоследних четырёх строк функции Max_Min перед оператором return value можно воспользоваться библиотечными функциями из stdlib.h Borland C++

value.max=max(value1.max, value2.max); value.min=min(value1.min, value2.min),

что сделает код программы более изящным, но если тип массива будет не int, то эти строки должны остаться без изменений. Структура pair введена для удобства записи кода программы.

Легко заметить, что сравнения элементов множества S происходят только в строках 1, 2, 3, помеченных символом 3. Пусть C(n) - число сравнений элементов множества S, которые надо произвести в процедуре MaxMin, чтобы найти наибольший и наименьший элементы множества S. Ясно, что C(2)=1. Если n >2, то C(n) - общее число сравнений, произведенных в двух вызовах функции MaxMin (строки h4 и h5), для множеств размера n/2, и ещё два сравнения в строках32 и 33. Следовательно:

(1.4)

Решением рекуррентных уравнений (1.4) является функция C(n)=n–2. Это легко доказать по индукции. Очевидно, что при n=2 эта функция удовлетворяет (1.4). Предположим, что при n=m³ 2 данная функция тоже является решением (1.4). Тогда

C(2m) = 2+ 2 = (2m) - 2,

т.е. функция C(n) удовлетворяет (1.4) при следующем значении n=2m. Значит, если n является степенью числа 2, то выбранная функция удовлетворяет рекуррентному соотношению (1.4).

В теории алгоритмов доказано, что для одновременного нахождения наибольшего и наименьшего элементов из n-элементного множества надо сделать не менее n–2 сравнений его элементов. Следовательно, предложенный алгоритм нахождения максимального и минимального элементов множества S оптимален в смысле числа сравнений между элементами из S, когда n есть степень 2.

Однако, хотя сам алгоритм и оптимален в смысле минимума сравнений между элементами, но его реализация на языке высокого уровня может уступать по временной сложности другим алгоритмам. В приведённом примере программа Max_Min_Element считает существенно быстрее, чем программа Max_Min, основанная на методе «разделяй и властвуй». Это происходит потому, что не учитываются сравнения в строке h6, когда проверяется размер массива, и не учитывается время расчёта указателей на крайние элементы массивов при их делении пополам. Всё же алгоритм с рекурсией в сочетании с «разделяй и властвуй» дает лучшие результаты в тех случаях, в которых время проверки размера множества существенно меньше времени сравнения элементов этого множества.

Обычно временная сложность процедуры определяется числом и размером подзадач и, в меньшей степени, работой, необходимой для разбиения данной задачи на подзадачи. Так как рекуррентные уравнения вида (1.4), (1.6) часто возникают при анализе рекурсивных алгоритмов типа «разделяй и властвуй», целесообразно рассмотреть решение таких уравнений в общем виде.

Теорема 1. Пусть a, b и c - неотрицательные постоянные. Решение рекуррентных уравнений

где n - степень числа c, имеют вид:

(1.8)

Доказательство. Если n - степень числа c (т.е. n=1, c, c² и т.д.), то легко проверить непосредственной подстановкой, что ряд

удовлетворяет условию теоремы. Пусть теперь a<c, тогда ряд в последнем равенстве сходится, и, следовательно, C(n) = O(n). Если a=c, то каждым членом ряда будет 1, а всего в нём O(logn) членов. Поэтому C(n) = O(n× logn). Наконец, если a>c, то

,

что составляет O(a^q), или O(n^r), где r=log_ca.ð

Из теоремы 1 вытекает, что разбиение задачи размера n (за линейное время) на две подзадачи размера n/2 даёт алгоритм сложности O(n×logn). Если бы подзадач было 3, 4 или 8, то получился бы алгоритм сложности порядка n^log3, n² или n³ соответственно. С другой стороны, разбиение задачи на 4 подзадачи размера n/2 даёт алгоритм сложности O(n×logn), а на 9 и 16 - порядка n^log3 и n² соответственно. Поэтому асимптотически более быстрый алгоритм умножения целых чисел можно было бы получить, если бы удалось так разбить исходные целые числа на 4 части, чтобы суметь выразить исходное умножение через 8 или менее меньших умножений.

Если n не является степенью числа c, то обычно можно вложить задачу размера n в задачу размера m, где m - наименьшая степень числа c, большая или равная n. Поэтому порядки роста, указанные в теореме 1, сохраняются для любого n.

1.8 Балансировка

В обоих примерах на технику “разделяй и властвуй” задача разбивалась на две подзадачи равных размеров. Это не было случайностью. Поддержание равновесия - основной руководящий принцип при разработке хорошего алгоритма. Для иллюстрации этого принципа рассмотрим пример из сортировки и сопоставим эффекты от разбиения задачи на подзадачи неравных размеров и подзадачи равных размеров. Но из этого примера не следует делать скоропалительный вывод о том, что балансировка (balancing) полезна только для техники “разде­ляй и властвуй”. В последующих разделах будут приведены примеры применения балансировки для решения других задач.

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

(1.9)

для числа сравнений, произведённых между сортируемыми элементами. Решением для (1.9) будет C(n)=n×(n-1)/2, что составляет O(n²).

Хотя это алгоритм можно считать рекурсивным применением приёма “разделяй и властвуй” с разбиением задачи на неравные части, он не эффективен для больших n. Для разработки асимптотически эффективного алгоритма сортировки надо позаботиться о сбалансированности. Вместо того чтобы разбивать задачу размера n на две подзадачи, одна из которых имеет размер 1, а другая - размер n-1, надо разбить её на две подзадачи с размерами примерно n/2. Это выполняется методом, известным под именем сортировка слиянием (merge sorting).

Рассмотрим последовательность целых чисел x₁, x₂, …, x_n. Пусть для простоты опять n есть степень числа 2. Один из способов упорядочить эту последовательность – разбить её на две подпоследовательности x₁, x₂, …, x_n/2 и x_(n/2)+1, x_(n/2)+2, …, x_n, упорядочить каждую из них и затем слить их. Под «слиянием» здесь понимается объединение двух уже упорядоченных последовательностей в одну упорядоченную последовательность.

Вход. Последовательность чисел x₁, x₂, …, x_n, где n=2^k, k - целое.

Выход. Последовательность y₁, y₂, …, y_n, являющаяся перестановкой входа и удовлетворяющая неравенствам y₁ £ y₂ £… £ y_n.

Метод. Задача сортировки элементов массива разбивается на две аналогичные задачи для массивов, каждый из которых представляет собой соответствующую половину исходного массива. Эту операцию осуществляет рекурсивная функция Sorting (Сортировка). Для слияния отсортированных массивов половинной длины используется функция Merge (Слияние), входом которой являются две упорядоченные последовательности S и T, а выходом - неубывающая последовательность элементов из S и T.