Отчет по практике: Информатика. Текстовый редактор

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

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

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

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

Пусть Т (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], 1in.

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

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

begin