Построение алгоритмов

Есть много стандартных приёмов, используемых при построении алгорит­мов. Сортировка вставками является примером алгоритма, действующего по шагам (incremental approach): мы добавляем элементы один за другим к отсор­тированной части массива.

В этом разделе мы покажем в действии другой подход, который называют «разделяй и властвуй» (divide-and-conquer approach), и построим с его помощью значительно более быстрый алгоритм сортировки.

 

Принцип «разделяй и властвуй»

Многие алгоритмы по природе своей рекурсивны (recursive): решая некото­рую задачу, они вызывают самих себя для решения её подзадач. Идея метода «разделяй и властвуй» состоит как раз в этом. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются (с помо­щью рекурсивного вызова — или непосредственно, если размер достаточно мал). Наконец, их решения комбинируются и получается решение исходной задачи.

Для задачи сортировки эти три этапа выглядят так. Сначала мы разби­ваем массив на две половины меньшего размера. Затем мы сортируем каждую из половин отдельно. После этого нам остаётся соединить два упорядоченных массива половинного размера в один. Рекурсивное разбиение задачи на мень­шие происходит до тех пор, пока размер массива не дойдёт до единицы (любой массив длины 1 можно считать упорядоченным).

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Оно выполняется с помощью вспомогательной процедуры Merge(A,p,q,r). Параметрами этой процедуры являются массив А и числа p,q,r, указывающие границы сливаемых участков. Процедура предполагает, что p≤q<r и что участки A[p..q] и A[q+1..r] уже отсортированы, и сливает (merges) их в один участок A[p..r].

Мы оставляем подробную разработку этой процедуры читателю (упр. 1.3-2), но довольно ясно, что время работы процедуры merge есть О(n), где n — общая длина сливаемых участков (n=r-p+1). Это легко объяснить на картах. Пусть мы имеем две стопки карт (рубашкой вниз), и в каждой карты идут сверху вниз в возрастающем порядке. Как сделать из них одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём ее (рубашкой вверх) в результирующую стопку. Когда одна из исходных стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке. Ясно, что каждый шаг требует ограниченного числа действий, и общее число действий есть Θ(n).

	2 5				4 6				1 3				2 6
			2 4 5 6								1 2 3 6
							1 2 2 3 4 5 6 6

Рис. 2. Сортировка слиянием для массива А = (5,2,4,6,1, 3,2,6).

 

Теперь напишем процедуру сортировки слиянием Merge-Sort(A, p, r), ко­торая сортирует участок А[р..r] массива А, не меняя остальную часть массива. При р≥ r участок содержит максимум один элемент, и тем самым уже отсор­тирован. В противном случае мы отыскиваем число q, которое делит участок на две примерно равные части A[р..q] (содержит [n/2 ˥ элементов) и A[q+1..r] (содержит [п/2˩ элементов). Здесь через [х˥ мы обозначаем целую часть х (наибольшее целое число, меньшее или равное х), а через [ х˩—наименьшее целое число, большее или равное х.

void Merge_Sort(Vector A, int p, int r)

{ int q;

if (p<r) {

q=(p+r)/2;

Merge_Sort(A,p,q);

Merge_Sort(A,q+1,r);

Merge(A,p,q,r); // Слияние сортированных подмассивов

} // A[p..q] и A[q+1,r]

}

Весь массив теперь можно отсортировать с помощью вызова Merge-Sort(A,1, length[A]). Если длина массива п=length[A] есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортирован­ные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до п (на последнем шаге соединяются два отсортированных участка длины п/2). Этот процесс показан на рис. 2.

В рекурсивном методе использованы:

const int maxn=100001;

typedef int Vector[maxn];

Vector A, b;

 

int Merge(Vector A, int p, int q, int r)

{ int i1, i2, i;

i1=p; i2=q+1; i=p;

while (i1<=q && i2<=r) {

if (A[i1]<=A[i2]) b[i++]=A[i1++];

else b[i++]=A[i2++];

}

while (i1<=q) b[i++]=A[i1++];

while (i2<=r) b[i++]=A[i2++];

for (i=p;i<=r;i++) A[i]=b[i];

return 0;

}

 

Анализ алгоритмов типа «разделяй и властвуй»

Как оценить время работы рекурсивного алгоритма? При подсчёте мы должны учесть время, затрачиваемое на рекурсивные вызовы, так что получа­ется некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.

Вот примерно как это делается. Предположим, что алгоритм разбивает за­дачу размера n на a подзадач, каждая из которых имеет в b раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений — времени C(n). Тогда получаем соотношение для времени работы T(n) на задачах размера n (в худшем случае): T(n)=aT(n/b)+D(n)+C(n). Это соотношение выполнено для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых п, когда такое разбиение невозможно или не нужно, применяется какой-то прямой метод решения задачи. Поскольку n огра­ничено, время работы тоже не превосходит некоторой константы.

 

 

Анализ сортировки слиянием

Для простоты будем предполагать, что размер массива есть степень двойки. Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени 0(1), а слияние — времени 0(n). Получаем соотношение

O(1), если n=1,

T(n)=

2T(n/2)+O(n), если n>1.

Докажем, что Т(n) = O(nlog n), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших n сортировка слиянием эффективнее сортировки вставками, требующей времени 0(n²).

Найдем верхнюю оценку для функции T(n)=2T(n/2)+n. Можно предположить, что T(n)= O(nlog n), т.е., что T(n)≤cnlogn для подходящего с>0. Докажем по индукции. Пусть эта оценка верна для [п/2˩, т.е. T ([п/2˩)≤ c [п/2˩ log ([п/2˩). Подставив ее в соотношение, получим

T(n)≤2(c [п/2˩ log ([п/2 ˩))+n≤cnlog(n/2)+n=cnlog(n)-cnlog(2)+n=cnlog(n)-cn+n≤cnlog(n).

Последний переход законен при c≥1.

Остается проверить базис индукции, т.е. доказать оценку для начального значения n. Поскольку [п/2˩≥ 2 при n>3, подберем c так, чтобы оценка T(n)≤cnlog(n) быда верна при n=2 и n=3.

Для проверки времени исполнения функций сортировки можно использовать функцию clock() c библиотеки #include <time.h>:

clock_t t0,tk;

t0=clock();

Merge_Sort(A,1,n);

t1=clock();

cout<<”t=”<<(t1-t0)/CLOCKS_PER_SEC<<endl;