Структуры данных и алгоритмы (1021739), страница 57
Текст из файла (страница 57)
Два описанных в этой главе алгоритма построенияостовных деревьев взяты из [67] и [88]. В работе [57] показано, как можно использовать частично упорядоченные деревья для реализации алгоритма Прима. В [17] и[123] представлены алгоритмы построения остовных деревьев с временной сложностьО(е log logn). В [109] предлагается исчерпывающий обзор и историческая справка поалгоритмам построения остовных деревьев.В [52] и [107] рассмотрены различные варианты применения метода поиска в глубину для алгоритмов, работающих с графами.
Алгоритм нахождения двусвязныхкомпонент взят из этих работ.Паросочетания графов изучались в [46], а чередующиеся цепи — в [10] и [27]. Вработе [51] приведен алгоритм нахождения максимального паросочетания для двудольных графов с временной сложностью О(п2'5), а в [75] — с временем выполненияO(J\ V \- \ Е |) для произвольных графов. Статья [82] содержит хорошее обсуждениепроблем паросочетании.•УПРАЖНЕНИЯ227ГЛАВА 8СортировкаСортировкой, или упорядочиванием списка объектов называется расположение этихобъектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение "<" для чисел.
Это очень большая тема, поэтомуона разбита на две части: внутреннюю и внешнюю сортировку. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, гдеможно получить доступ к данным в любом порядке (т.е. используется модель памяти спроизвольным доступом). Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно было поместить воперативную память. Здесь узким местом является механизм перемещения большихблоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Тот факт, что физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, заставляет нас применять разнообразные методы внешней сортировки. Эти методы будут рассмотрены в главе 11.'...• • .'8.1.
Модель внутренней сортировки•.В этой главе мы представим основные принципиальные алгоритмы внутреннейсортировки. Простейшие из этих алгоритмов затрачивают время порядка О(п2) дляупорядочивания п объектов и потому применимы только к небольшим множествамобъектов. Один из наиболее популярных алгоритмов сортировки, так называемая быстрая сортировка, выполняется в среднем за время О(п logra).
Быстрая сортировкахорошо работает в большинстве приложений, хотя в самом худшем случае она такжеимеет время выполнения О(п2). Существуют другие методы сортировки, такие какпирамидальная сортировка или сортировка слиянием, которые в самом худшем случае дают время порядка О(п logra), но в среднем (в статистическом смысле) работаютне лучше, чем быстрая сортировка. Отметим, что метод сортировки слиянием хорошоподходит для построения алгоритмов внешней сортировки. Мы также рассмотрималгоритмы другого типа, имеющие общее название "карманной" сортировки.
Эти алгоритмы работают только с данными определенного типа, например с целыми числами из ограниченного интервала, но когда их можно применить, то они работаюточень быстро, затрачивая время порядка О(п) в самом худшем случае.Всюду в этой главе мы будем предполагать, что сортируемые объекты являютсязаписями, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка"<". Целые и действительные числа, символьные массивы — вот общие примеры таких типов данных, но, конечно, мы можем использовать ключи других типов данных, лишь бы на них можно было определить отношение "меньше чем" или "меньшечем или равно".Задача сортировки состоит в упорядочивании последовательности записей такимобразом, чтобы значения ключевого поля составляли неубывающую последовательность. Другими словами, записи г1; г2, ...» г„ со значениями ключей klt k2, ..., kn надорасположить в порядке г^, г^,..., rt , таком, что k^ <k^< ...
< &, . Мы не требуем,чтобы все записи были различными, и если есть записи с одинаковыми значениямиключей, то в упорядоченной последовательности они располагаются рядом друг сдругом в любом порядке.Мы будем использовать различные критерии оценки времени выполнения алгоритмов внутренней сортировки. Первой и наиболее общей мерой времени выполнения является количество шагов алгоритма, необходимых для упорядочивания л записей.
Другой общей мерой служит количество сравнений между значениями ключей, выполняемых при сортировке списка из п записей. Эта мера особенноинформативна, когда ключи являются строками символов, и поэтому самым"трудоемким" оператором будет оператор сравнения ключей. Если размер записейбольшой, то следует также учитывать время, необходимое на перемещение записей.При создании конкретных приложений обычно ясно, по каким критериям нужнооценивать применяемый алгоритм сортировки.8.2. Простые схемы сортировкиПо-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы описать основную идею этого метода, представим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально.
Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, беретсяпервая запись массива и ее ключ поочередно сравнивается с ключами последующихзаписей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится"эталоном" для сравнения, и все последующие записи сравниваются с этим новым,более "легким" ключом. В результате запись с наименьшим значением ключа-окажется в самом верху массива.
Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденнойпри первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что вовремя второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи,меньшие, чем у оставшихся записей. Другими словами, во время i-ro прохода непроверяются записи, стоящие на позициях выше i. В листинге 8.1 приведен описываемый алгоритм, в котором через А обозначен массив из п записей (тип данных геcordtype).
Здесь и далее в этой главе предполагаем, что одно из полей записей называется key (ключ) и содержит значения ключей.Листинг 8.1. Алгоритм „пузырька"(1)(2)(3)(4)for i : = l t o n - l d ofor j: = 1 down-to i + 1 doif A[j].key < A [ j - 1].key thens w a p U t j ] , A [ j - 1])Процедура swap (перестановка) используется во многих алгоритмах сортировкидля перестановки записей местами, ее код показан в следующем листинге.Листинг 8.2. Процедура swapprocedure swap ( var x, у: recordtype ){ swap меняет местами записи x тл у }vartemp: recordtype;begintejnp:= x;x:- y;y: = temp;end; { swap }8.2.
ПРОСТЫЕ СХЕМЫ СОРТИРОВКИПример 8.1. В табл. 8.1 приведен список названий и годы знаменитых извержений вулканов.Таблица 8.1. Знаменитые извержения вулкановНазваниеГодПилиЭтнаКракатауАгунгСв. ЕлеваВезувий1902166918831963198079Для этого примера мы применим следующее объявление типов данных:typekeytype = array[1..10] of char;recordtype = recordkey: keytype; { название вулкана }year: integer { год извержения }end;Применим алгоритм "пузырька" для упорядочивания списка вулканов в алфавитномпорядке их названий, считая, что отношением линейного порядка в данном случае является отношение лексикографического порядка над полем ключей.
В табл. 8.2 показаныпять проходов алгоритма (в данном случае п = 6). Линии указывают позицию, выше которой записи уже упорядочены. После пятого прохода все записи, кроме последней, стоятна нужных местах, но последняя запись не случайно оказалась последней — она такжеуже стоит на нужном месте. Поэтому сортировка заканчивается.Таблица 8-2.
Сортировка методом „пузырька"ПилиЭтнаКракатауАгунгСв. ЕленаВезувийАгунгПилиЭтнаКракатауВезувийСв. ЕленаАгунгВезувийПилиЭтнаКракатауСв. ЕленаАгунгВезувийКракатауПилиЭтнаСв. ЕленаАгунгВезувийКракатауПилиСв. ЕленаЭтнаАгунгВезувийКракатауПилиСв. ЕленаЭтнаНачальное положение1-й проход2-й проход3-й проход4-й проход5-й проходНа первом проходе Везувий и Св. Елена меняются местами, но далее Везувий неможет поменяться местами с Агунгом. Агунг, поочередно меняясь местами с Кракатау, Этной и Пили, поднимается на самый верх. На втором этапе Везувий поднимается вверх и занимает вторую позицию.
На третьем этапе это же проделывает Кракатау, а на четвертом — Этна и Св. Елена меняются местами, Пили стоит на нужномместе. Все названия вулканов расположились в алфавитном порядке, сортировка закончилась. Пятый этап также выполнен в соответствии с алгоритмом листинга 8.1,но он уже не меняет порядок записей. ПГЛАВА 8. СОРТИРОВКАСортировка вставкамиВторой метод, который мы рассмотрим, называется сортировкой вставками, таккак на i-м этапе мы "вставляем" 1-й элемент A[i] в нужную позицию среди элементов А[1], А[2], ..., A[i - 1], которые уже упорядочены. После этой вставки первые iэлементов будут упорядочены. Сказанное можно записать в виде следующей псевдопрограммы:for i:= 2 to л doпереместить A[i] на позицию j S i такую, чтоA [ i ] < A [ k ] для j £ k < i илибо A[i] S A[j - 1], либо j = 1Чтобы сделать процесс перемещения элемента A[i] более простым, полезно ввести элемент А[0], чье значение ключа будет меньше значения ключа любого элемента А[1], ..., А[п].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
