Информатика. Текстовый редактор (стр. 3 из 5)

Алгоритм 3.3. Построение сортирующего дерева

Вход. Массив элементов A[i], 1

Выход. Элементы массива А, организованные в виде сортирующего дерева, т. е.A[i]

] для 1<i

Метод. В основе алгоритма лежит рекурсивная процедура пересыпка. Ее параметры i и j задают область ячеек массива А, обладающую свойством сортирующего дерева; корень строящегося дерева помещается в i.

procedure ПЕРЕСЫПКА ((i,j):

1. ifi — не лист и какой-то его сын содержит элемент, превосходящий элемент в ithenbegin

2. пусть k— тот сын узла i, в котором хранится

наибольший элемент;

3. переставить А[i] и А[k];

4. ПЕРЕСЫПКА (k,j)

5. end

Параметр j используется, чтобы определить, является ли i листом и имеет он одного или двух сыновей. Если i > j/2, то i — лист, и процедуре ПЕРЕСЫПКА(i,j) ничего не нужно делать, поскольку А[i] — уже сортирующее дерево.

Алгоритм, превращающий весь массив А в сортирующее дерево, выглядит просто:

procedure ПОСТРСОРТДЕРЕВА:

for i

п¹) stер —1 until 1 do ПЕРЕСЫПКА (i,n)

Покажем, что алгоритм 3.3 преобразует А в сортирующее дерево за линейное время.

Лемма 3.2. Если узлы i+1, i+2, . . ., n являются корнями сортирующих деревьев, то после вызова процедуры ПЕРЕСЫПКА (i, п) все узлы i, i+1, . . ., п будут корнями сортирующих деревьев.

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

Базис, т. е. случай i=п, тривиален, так как узел п должен быть листом и условие, проверяемое в строке 1, гарантирует, что ПЕРЕСЫПКА (п, п) ничего не делает.

Для шага индукции заметим, что если i — лист или у него нет сына с большим элементом, то доказывать нечего (как и при обосновании базиса). Но если у узла i есть один сын (т. е. если 2i=n) и A[i]<A[2i], то строка 3 процедуры ПЕРЕСЫПКА переставляет А[i] и А[2i]. В строке 4 вызывается ПЕРЕСЫПКА (2i, n); поэтому из предположения индукции вытекает, что дерево с корнем 2i будет переделано в сортирующее. Что касается узлов i+1, i+2, . . . . . ., 2i — 1, то они и не переставали быть корнями сортирующих деревьев. Так как после этой новой перестановки в массиве А выполняется неравенство A[i]>A[2i], то дерево с корнем i также оказывается сортирующим.

Аналогично, если узел i имеет двух сыновей (т. е. если 2i+1

n) и наибольший из элементов в А [2i] и в А [2i+1] больше элемента в A [i], то, рассуждая, как и выше, можно показать, что после вызова процедуры ПЕРЕСЫПКА(i,n) все узлы i, i+1,..., n будут корнями сортирующих деревьев.

Теорема 3.5. Алгоритм 3.3 преобразует А в сортирующее дерево за линейное время.

Доказательство. Применяя лемму 3.2, можно с помощью простой возвратной индукции по i показать, что узел i становится корнем какого-нибудь сортирующего дерева для всех i, 1

Пусть Т (h) — время выполнения процедуры ПЕРЕСЫПКА на узле высоты h. Тогда Т (h)

Т (h — 1)+с для некоторой постоянной с. Отсюда вытекает, что Т (h) есть О (h).

Алгоритм 3.3 вызывает процедуру ПЕРЕСЫПКА, если не считать рекурсивных вызовов, один раз для каждого узла. Поэтому время, затрачиваемое на ПОСТРСОРТДЕРЕВА, имеет тот же порядок, что и сумма высот всех узлов. Но узлов высоты i не больше, чем

. Следовательно, общее время, затрачиваемое процедурой ПОСТРСОРТДЕРЕВА, имеет порядок

in/2

, т.е O(n)

Теперь можно завершить детальное описание алгоритма СОРТДЕРЕВОМ. Коль скоро элементы массива А преобразованы в сортирующее дерево, некоторые элементы удаляются из корня по одному за раз. Это делается перестановкой А[1] и А[n] и последующим преобразованием A[1], А[2], ..., А[n - 1] в сортирующее дерево. Затем переставляются А[1] и А[n - 1], а A[1], А[2], ..., А [п - 2] преобразуется в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда А[1], А[2], ..., А[n] — упорядоченная последовательность.

Алгоритм 3.4. Сортдеревом

Вход. Массив элементов А[i], 1

Выход. Элементы массива А, расположенные в порядке неубывания.

Метод. Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм 3.3. Наш алгоритм выглядит так:

begin

ПОСТРСОРТДЕРЕВА;

Fori

nstep -1 until 2 do

Begin

переставить А[1] и А[i];

ПЕРЕСЫПКА(i,i - 1)

End end

Теорема 3.6.Алгоритм 3.4 упорядочивает последовательность из п элементов за время 0(nlogп).

Доказательство. Корректность алгоритма доказывается индукцией по числу выполнений основного цикла, которое обозначим через m. Предположение индукции состоит в том, что после m итераций список A[n-m+1], ..., А [n] содержит m наибольших элементов, расположенных в порядке неубывания, а список A[1], ..., А[n-m] образует сортирующее дерево. Детали доказательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, i) есть 0(logi)- Следовательно, алгоритм 3.4 имеет сложность О (nlogi ).

Следствие. Алгоритм Сортдеревом имеет временную сложность O

(nlogn)

3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ О(nlogn)

До сих пор мы рассматривали поведение сортирующих алгоритмов только в худшем случае. Для многих приложений более реалистичной мерой временной сложности является усредненное время работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь среднюю временную сложность, существенно меньшую n 1оgn. Однако известны алгоритмы сортировки, которые работают в худшем случае сn² времени, где с — некоторая постоянная, но среднее время работы, которых относит их к лучшим алгоритмам сортировки. Примером такого алгоритма служит алгоритм Быстрсорт, рассматриваемый в этом разделе.

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

Общий метод состоит в том, чтобы поставить в соответствие каждому листу v дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям. Таким образом, можно определить среднее число сравнений, производимых данным алгоритмом сортировки, если вычислить сумму взятую по всем листьям дерева решений данного алгоритма, в которой р_i — вероятность достижения i-го листа, а d

, - его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4.

Теорема 3.7. В предположении, что все перестановки п-элементной последовательности появляются на входе с равными вероятностями, любое дерево решений, упорядочивающее последовательность из п элементов, имеет среднюю глубину не менее logn!.

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

mlogm.

Базис, т. е. случай /п=1, тривиален. Допустим, что предположение индукции верно для всех значений m, меньших k. Рассмотрим дерево решений Т с и листьями. Оно состоит из корня с левым поддеревом Т с k листьями и правым поддеревом T

с k – 1 листьями при некотором i, 1

k. Ясно, что

D(T)=i+D(T

)+(k-i)+D(T

)

Поэтому наименьшее значение D (Т) дается равенством

D(k)=

[k+D(i)+D(k-1)]. (3.1)

Учитывая предположение индукции, получаем отсюда

D(k)

[i log i+(k-i)log(k-i)] (3.2)

Легко показать, что этот минимум достигается при i=k/2. Следовательно, D(k)

k+klog

=klogk

Таким образом, D (m)

mlogm для всех m