1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 21
Текст из файла (страница 21)
1вз гл. в. согтиговкд и погядковыа сгдтистики 3.4. СОРТДЕРЕВОМ вЂ” УПОРЯДОЧЕНИИ С ПОМОЩЬЮ 0(п 1оЕ и) СРАВНЕНИЯ Так как любой сортирующий алгоритм, упорядочивающий с помощью сравнений, затрачивает по необходимости а 1ой л сравнений для упорядочения хотя бы одной последовательности длины и, естественно спросить, существуют ли сортирующие алгоритмы, затрачивающие ие более 0(п 1ой п) сравнений для упорядочения любой последовательности длины л.
Один такой алгоритм мы уже видели — это сортировка слиянием из разд. 2.7, Другой алгоритм— Сортдеревом. Помимо того, что это полезный алгоритм упорядочения, в нем используется интересная структура данных, которая находит н другие приложения. Сортдеревом лучше всего понять в терминах двоичного дерева вроде изображенного на рис. 3.5, у которого каждый лист имеет глубину с( или с( — 1. Узлы дерева помечаются элементами последовательности, которую хотят упорядочить.
Затем Сортдеревом меняет размещение этих элементов на дереве до тех пор, пока элемент, соответствующий произвольному узлу, станет не меньше элементов, соответствующих его сыновьям. Такое помеченное дерево мы будем называть сортирующим. Пример 3.3. На рис. 3,5 изображено сортирующее дерево.
Заметим, что последовательность элементов, лежащих на пути из любого листа в корень, линейно упорядочена и наибольший элемент в поддереве всегда соответствует его корню. П На следующем шаге алгоритма Сортдеревом из сортирующего дерева удаляется наибольший элемент — он соответствует корню дерева. Метка некоторого листа переносится в корень, а сам лист удаляется. Затем полученное дерево переделывается в сортирующее, и процесс повторяется. Последовательность элементов, удаленных из сортирующего дерева, упорядочена по невозрастанию. Удобной структурой данных для сортирующего дерева служит такой массив А, что АН1 — элемент в корне, а А1211 и А121+11— Рве. 3.5. Сортируюдее дерево. $06 хс сОРтдвгезом элементы в левом и правом сыновьях (если они существуют) того узла, в котором хранится АИ.
Например, сортирующее дерево на рис. 3.5 можно представить массивом Заметим, что узлы наименьшей глубины стоят в этом массиве первыми, а узлы равной глубины стоят в порядке слева направо. Не каждое сортирующее дерево можно представить таким способом. На языке представления деревьев можно сказать, что для образования такого массива требуется, чтобы листья самого ннз.
кого уровня стояли как можно левее (как„например, иа рнс. 3.5). Если сортирующее дерево представляется описанным массивом, то некоторые операции нз алгоритма Сортдеревом легко выполнить. Например, согласно алгоритму, нужно удалить элемент из корня, где-то запомнить его, переделать оставшееся дерево в сортирующее и удалить непомеченный лист. Можно удалить наибольший элемент из сортирующего дерева и запомнить его, поменяв местами А[1] и А[п], н затем не считать более ячейку и нашего массива частью сортирующего дерева. Ячейка и рассматривается как лист, удаленный из этого дерева.
Для того чтобы переделать дерево, хранящееся в ячейках 1,2,..., и — 1, в сортирующее, надо взять новый элемент А[1] и провести его вдоль подходящего пути в дереве. Затем можно повторить процесс, меняя местами А[!] и А[л — 1] и считая, что дерево занимает ячейки 1, 2,..., а — 2 н т. д. Пример 3.4. Рассмотрим на примере сортирующего дерева рис.
3.5, что происходит, когда мы поменяем местами первый н последний элементы массива, представляющего это дерево. Новый массив соответствует помеченному дереву на рис. 3.6,а. Элемент 16 исключается из дальнейшего рассмотрения. Чтобы превратить полученное дерево в сортирующее, надо поменять местами элемент 4 с ббльшим нз его сыновей, т. е. с элементом 11. В своем новом положении элемент 4 обладает сыновьями 1О и 6.
Так как они больше 4, то 4 переставляется с 10, ббльшим сыном. После этого сыновьями элемента 4 в новом положении становятся 1 и 2. Поскольку 4 превосходит их обоих, дальнейшие перестановки не нужны. 407 Гл. 3. совтинонкл и ИОРядконые стАтистики Рис. 3.6. а — результат перестановки злементов 4 и 16 в сортируюпгем дереве рис. 3.5; б — результат перестройки сорти рующего дерева и удаления злемента ! 6.
Полученное в результате сортирующее дерево показано на рис. З.б,б. Заметим, что хотя элемент 16 был удален из сортирующего дерева, он все же присутствует в конце массива А. С[ Теперь перейдем к формальному описанию алгоритма Сорт- деревом. Пусть а„ аю ..., а„ вЂ” последовательность сортируемых элементов. Предположим, что вначале они помещаются в массив А именно в этом порядке, т, е. А И=ам 1<1<и. Первый шаг состоит в построении сортирующего дерева, т. е. элементы в А перераспределяются так, чтобы удовлетворялось свойство сортируюм[гго дерева: АИ>А[211 при 1<1<лг2 н АИ>А[2[+11 при 1<г<л!2. Это делают, строя, начиная с листьев, все большие и большие сортирующие деревья. Всякое поддерево, состоящее нз листа, уже является сортирующим.
Чтобы сделать поддерево высоты [т сортирующим, надо переставить элемент в корне с наибольшим из элементов, соответствующих его сыновьям, если, конечно, он меньше какого-то из них. Такое действие может испортить сортнрующее дерево высоты Ь вЂ” 1, и тогда его надо снова перестроить в сортирующее. Приведем точное описание этого алгоритма. Алгоритм З.З, Построение сортирующего дерева Вход.
Массив элементов АИ, 1<[<л. Выход. Элементы массива А, организованные в виде сортирую- щего дерева, т. е. АИ<А1 [ и/2 ~ [ для 1<1<и. Метод. В основе алгоритма лежит рекурсивная процедура ПЕРЕСЫПКА. Ее параметры 1 н [ задают область ячеек массива А, обладающую свойством сортирующего дерева; корень строящегося дерева помещается в й а.и соптдк квом ргоседпге ПЕРЕСЫПКА (1, /): 1. И ! — не лист и какой-то его сын содержит элемент, превосходящий элемент в ! [пеп Ьей[п 2. пусть й — тот сын узла 1, в котором хранится наибольший элемент; 3. переставить А[!1 и А[йф 4.
ПЕРЕСЫПКА(й, !) епд Параметр 1 используется, чтобы определить, является ли 1 листом и имеет ои одного или двух сыновей. Если !))/2, то !— лист, и процедуре ПЕРЕСЫПКА(1, !) ничего не нужно делать, поскольку АИ вЂ” уже сортирующее дерево. Алгоритм, превращающий весь массив А в сортирующее дерево, выглядит просто: ргоседпге ПОСТРСОРТДЕРЕВА: 1ог ! -и') з1ер — 1 пп!11 ! до ПЕРЕСЫПКА(1, и) [ ! Покажем, что алгоритм З.З преобразует А в сортирующее дерево за линейное время.
Лемма 3.2. Если узлы !+1, !+2,..., п являются корнями сортирующих деревьев, то после вызова процедуры ПЕРЕСЫПКА (1, н) все узлы 1, !+1,..., п будут корнями сортирующих деревьев. Д о к а з а т е л ь с т в о. Доказательство проводится возвратной индуицией по !. Базис, т. е. случай (=п, тривиален, так как узел л должен быть листом и условие, проверяемое в строке 1, гарантирует, что ПЕРЕСЫПКА(п, и) ничего не делает. Для шага индукции заметим, что если ! — лист или у него нет сына с большим элементом, то доказывать нечего (каи и при обосновании базиса). Но если у узла 1 есть один сын (т.
е. если 2(=п) и А[1[(А[2![, то строка 3 процедуры ПЕРЕСЫПКА переставляет АИ и А[2([. В строке 4 вызывается ПЕРЕСЫПКА(21, и); поэтому из предположения индукции вытекает, что дерево с корнем 21 будет переделано в сортирующее. Что касается узлов 1+1, 1+2, ... ..., 2! — 1, то они и не переставали быть корнями сортирующих деревьев. Так как после этой новой перестановки в массиве А выполняется неравенство А[!))А[21[, то дерево с корнем ! также оказывается сортирующим.
Аналогично, если узел ! имеет двух сыновей (т, е. если 2!+1(л) и наибольший из элементов в А[2![ и в А[2!+![ больше элемента т! На практике иы бы начали с 1 и!2 1, гл. а согтиговкл и погядковыя статистики в А[11, то, рассуждая, как и выше, можно показать, что после вызова процедуры ПЕРЕСЫПКА(1, л) все узлы 1, 1+1,..., и будут корнями сортирующих деревьев.
П Теорема 3.5. Алгоритм 3.3 преобразует А в сортируюи(ее дерево за линейное время. Д о к а з а тел ь с тв о. Применяя лемму 3.2, можно с помощью простой возвратной индукции по 1 показать, что узел 1 становится корнем какого-нибудь сортирующего дерева для всех 1, 1(1(л. Пусть Т(л) — время выполнения процедуры ПЕРЕСЫПКА на узле высоты й. Тогда Т (л)(Т (л — 1)+с для некоторой постоянной с. Отсюда вытекает, что Т(Ь) есть 0(й). Алгоритм З.З вызывает процедуру ПЕРЕСЫПКА, если не считать рекурсивных вызовов, один раз для каждого узла.
Поэтому время, затрачиваемое на ПОСТРСОРТДЕРЕВА, имеет тот же порядок, что и сумма высот всех узлов. Но узлов высоты 1 не больше, чем [ л(2г+' [. Следовательно, общее время, затрачиваемое процедурой ПОСТРСОРТДЕРЕВА, имеет порядок ~(л/2', т. е. 0(л). П гГ1 Теперь можно завершить детальное описание алгоритма СОРТ- ДЕРЕВОМ. Коль скоро элементы массива А преобразованы в сортирующее дерево, некоторые элементы удаляются из корня по одному за раз.
Это делается перестановкой АП1 н А[л1 и последующим преобразованием А[1], А[21, ..., А[л — 11 в сортирующее дерево. Затем переставляются А[1! и А[л — 11, а АШ, А[21, ..., А[и — 21 преобразуется в сортирующее дерево. Процесс продолжается до тех пор, пока в сортнрующем дереве не останется один элемент. Тогда А[11, А[21, ..., А[л! — упорядоченная последовательность. Алгоритм 3.4. Сортдеревом Вход. Массив элементов А[11, 1(1(л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
