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

Алгоритм, упорядочивающий с помощью сравнений, можно представить в виде дерева решений так, как описано в разделе 1.5. На рис. 1.18 изображено дерево решений, упорядочивающее последовательность a, b, c. Далее мы предполагаем, что если элемент a сравнивается с элементом b в некотором узле v дерева решений, то надо перейти к левому сыну узла v при a < b и к правому — при a

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

Лемма 3.1. Двоичное дерево высоты Н содержит не более 1^п листьев.

Доказательство. Элементарная индукция по h. Нужно лишь заметить, что двоичное дерево высоты h составлено из корня и самое большее двух поддеревьев, каждое высоты не более h - 1 .

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

Доказательство. Так как результатом упорядочения последовательности из п! элементов может быть любая из п\ перестановок входа, то в дереве решений должно быть по крайней мере n! листьев. По лемме 3.1 высота такого дерева должна быть не меньше logn!.

Следствие. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из п элементов тратится не меньше сп log п сравнений при некотором с>0 и достаточно большом п.

Доказательство. Заметим, что при n >1

n(n-1)(n-2)…(

)

(

)

так что logn!

(n/2)log(n/2)

(n/4)log n при n

По формуле Стирлинга точнее приближает n!функция (п/е)^п, так что n(log п — log е)=п log п — 1,44n служит хорошим приближением нижней границы числа сравнений, необходимых для упорядочения последовательности из п элементов.

3.4. СОРТ ДЕРЕВОМ — УПОРЯДОЧЕНИЕ С ПОМОЩЬЮ О(nlogn) СРАВНЕНИЙ

Так как любой сортирующий алгоритм, упорядочивающий с помощью сравнений, затрачивает по необходимости п log п сравнений для упорядочения хотя бы одной последовательности длины n, естественно спросить, существуют ли сортирующие алгоритмы, затрачивающие не более О (п log п) сравнений для упорядочения любой последовательности длины п. Один такой алгоритм мы уже видели — это сортировка слиянием из разд. 2.7. Другой алгоритм — Сортдеревом. Помимо того, что это полезный алгоритм упорядочения, в нем используется интересная структура данных, которая находит и другие приложения.

Сортдеревом лучше всего понять в терминах двоичного дерева вроде изображенного на рис. 3.5, у которого каждый лист имеет глубину d. или d-1. Узлы дерева помечаются элементами последовательности, которую хотят упорядочить. Затем Сортдеревом меняет размещение этих элементов на дереве до тех пор, пока элемент, соответствующий произвольному узлу, станет не меньше элементов, соответствующих его сыновьям. Такое помеченное дерево мы будем называть сортирующим.

Пример 3.3. На рис. 3.5 изображено сортирующее дерево. Заметим, что последовательность элементов, лежащих на пути из любого листа в корень, линейно упорядочена и наибольший элемент в поддереве всегда соответствует его корню.

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

Удобной структурой данных для сортирующего дерева служит такой массив А, что А[1] — элемент в корне, а А[2i] и A[2i+1] – элементы в левом и правом сыновьях (если они существуют) того узла, в котором хранится А[i].

Рисунок 3.5 Сортирующее дерево.

Например, сортирующее дерево на рис. 3.5 можно представить массивом

Заметим, что узлы наименьшей глубины стоят в этом массиве первыми, а узлы равной глубины стоят в порядке слева направо.

Не каждое сортирующее дерево можно представить таким способом. На языке представления деревьев можно сказать, что для образования такого массива требуется, чтобы листья самого низкого уровня стояли как можно левее (как, например, на рис. 3.5).

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

Пример 3.4. Рассмотрим на примере сортирующего дерева рис. 3.5, что происходит, когда мы поменяем местами первый и последний элементы массива, представляющего это дерево. Новый массив

соответствует помеченному дереву на рис. 3.6,а. Элемент 16 исключается из дальнейшего рассмотрения. Чтобы превратить полученное дерево в сортирующее, надо поменять местами элемент 4 с большим из его сыновей, т. е. с элементом 11.

В своем новом положении элемент 4 обладает сыновьями 10 и 5. Так как они больше 4, то 4 переставляется с 10, большим сыном. После этого сыновьями элемента 4 в новом положении становятся 1 и 2. Поскольку 4 превосходит их обоих, дальнейшие перестановки не нужны.

Рисунок 3.6. а — результат перестановки элементов 4 и 16 в сортирующем дерев

Рисунок 3.6; б — результат перестройки сортирующего дерева и удаления элемента 16.

Полученное в результате сортирующее дерево показано на рис. 3.6,6. Заметим, что хотя элемент 16 был удален из сортирующего дерева, он все же присутствует в конце массива А .

Теперь перейдем к формальному описанию алгоритма Сорт-деревом.

Пусть а_г, а₂, . . ., а_п — последовательность сортируемых элементов. Предположим, что вначале они помещаются в массив А именно в этом порядке, т. е. A[i] = a

n. Первый шаг состоит в построении сортирующего дерева, т. е. элементы в А перераспределяются так, чтобы удовлетворялось свойство сортирующего дерева: A[i]

A[2i] при 1

n/2 и A[i]

A[2i+1] при 1

n/2. Это делают, строя, начиная с листьев, все большие и большие сортирующие деревья. Всякое поддерево, состоящее из листа, уже является сортирующим. Чтобы сделать поддерево высоты h сортирующим, надо переставить элемент в корне с наибольшим из элементов, соответствующих его сыновьям, если, конечно, он меньше какого-то из них. Такое действие может испортить сортирующее дерево высоты h — 1, и тогда его надо снова перестроить в сортирующее. Приведем точное описание этого алгоритма.