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

-* 18 -* всплытие 66 -> перестановка -> 56

/ \ / \ / \

65 66 65 63 65 63

А /\ А /\ А /

4 37 63 56 4 37 18 56 4 37 18 66

почти упорядоченное дерево всплытие ~>5 перестановка 18 всплытие -* 63

56 63 56 63 56 18

А /\ А А

4 37 18 66 4 37 65 66 4 37 65 66

перестановка -> 37 > всплытие ► 56 -> перестановка 4

56 18 37 18 37 18 / /

4 63 65 66 4 63 65 66 56 63 65 66

всплытие -> 37 перестановка - - 18 -> всплытие -* 18

4 18 4 37 4 37

56 63 65 66 56 63 65 66 56 63 65 66

перестановка 4

18 37

56 63 65 66 >fc -63 *63 -(.6

Рис. 5.5. Пример сортировки чисел 18,4.56,65,37,63,66 методом Флойда

Алгоритм 5.5. Сортировка всплытием Флойда сложности 0(n\og2n) Program { Сортировка по возрастанию

всплытием Флойда }

uses CRT;

const n = 1000; {Размер массива данных для сортировки) type

Vector = array[l..n] of Integer; Var

f -.Text; {Текстовый файл для результатов сортировки}

procedure var a: vector; n: integer);

{ Заполнить вектор all. .ft] случайными числами } var

i: integer; begin

Randomize;

for i:=l to n do a[i]:=Random(100);

end;

procedure var a: Vector; i,k: integer);

{ Процедура всплытия Флойда по дереву а [i..k] } var

j,m,copy :Integer;

begin

copy:=a[i]; m:=2*i;

while m<=k do begin if m=k then j:=m

else if a[m]>a[m+l] then j:=melse j:=m+l;

if a[j]>copy then begin a[i]:=a [ j]; i : = j ; m:=2*i;

else break; {выход из цикла) end;

a[i]:=copy;

end;

procedure var

{ Сортировка вектора a [1. .n] методом Флойда } var

i,k,w :Integer; begin

{Формировать исходное частично упорядоченное дерево) for i:=n div 2 downto 2 do Surface(a,i,n) ; {Выполнить процедуру всплытия Флойда

для каждого поддерева) for k:=n downto 2 do begin Surface(a,1,k);

{Поместить найденный максимальный элемент

в конец списка) w:=a[k]; a[k]:=a[l]; a[l]:=w;

end;

Var {Main)

а : Vector; {Вектор исходных данных для сортировки) i : Integer; begin; {Main}

Assign(f,sort.out);

Rewrite(f); (Файх открыт для записи)

Init(a,n);

{Сохранить исходные данные)

for i:=l to n do WriteLn(f,a[ \ i;1,]=,a[i] :3); Sort(a,n);

{Сохранить сортированные данные} WriteLn(f);

for i:=l to n do WriteLn(£, s[\i:l, )--- ,a [i] Close(f); end. (Main)

Оценим общую сложность алгоритма сортировки данных рассматриваемым методом. Процедура SURFACE всплытия Флойда выполняется п раз сначала для формирования исходного почти упорядоченного дерева (процедура применяется для каждой вершины дерева) и затем п раз для всплытия каждого наибольшего (наименьшего) элемента в почти упорядоченном дереве. Так как сложность процедуры SURFACE всплытия Флойда составляет

общая сложность алгоритма сортировки данных 2. - . ан равна O(nlogin).

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

равно и только одна из них удовлетворяет условию нашей сортировки. Двоичный же поиск перестановки среди множества й! перестановок требует log2n! числа сравнений. Для упрощения воспользуемся формулой Стирлинга п\~ 2дтпп е~п. Тогда log2 ! ~2ттппе-п =0(п\о%гп).

Задача. Длина объединения отрезков. Текстовый файл содержит целые числа: Данная последовательность чисел определяет на прямой п отрезков \at,b\, i- 1,2..... п. Найти

длину объединения указанных отрезков. Исходные данные представлены в текстовом файле со следующей структурой. Первая

строка файла: п - количество отрезков. Вторая, третья и т.д. строки файла содержат целые числа а Ь, - границы соответствующих отрезков. Результаты расчетов длины объединения отрезков сохранить в текстовом файле.

Пример файла исходных данных:

з

О 2 -1 1

Пример файла выходных данных:

з

Решение. Алгоритм 5.6 решения задачи основывается на предварительной сортировке абсцисс ал, Ьь а2, Ь2,..., а„, Ьп в массиве аЬ[\..2п]. Создается вспомогательный массив g[\..2n], который поддерживает после сортировки массива ab[\..2n отношение границ отрезков: £[/ = 1 - левая граница, g[i] = 0 - правая граница. Вычисление завершается простым просмотром массива вЪ\\..2п] за линейное время. Общая сложность алгоритма определяется сложностью сортировки данных. В данном случае используется алгоритм пузырьковой сортировки сложности 0(п2).

Алгоритм 5.6. Программа расчета длины объединения отрезков

Program MeasureLength; {Длина объединения отрезков)

uses CRT,DOS; const n max=100; type

Vector=array[0..2*n max] of Integer; var

f :Text; {Текстовый файл)

ab :Vector; {Гранинь отрезков alii, b[i] :

g :Vector; {Признак!- границ: 1-левая, 0-лравая)

Procedure Measure( Var Longlnt; n:Integer );

{Расчет объединения)

i, с : Integer; begin

ab[0]:=ab[1];

m:=0; {Длина объединения)

c:=0; {Числе перекрывающихся интервалов}

for i:=l to n do begin

if cOO then m:=m+ab[i] -ab[i-l] ;

if g[i]=l {-левая граница) then c:=c+l else c:=c-l; end;

end;

Procedure SortBubble( n:Integer ) ;

{Сортировка границ а[i],b[Ц и g[i]) Var i,j,w :Integer;

begin

for i:=l to n do begin for j:=l to n-i do begin

if ab[j] > ab[j+l] then begin

w:=ab[j]; ab[j]:=ab[j+1]; ab[j+l]:=w; w:=g[j]; g[j]:=g[j+1]; g[j+l]:=w; end; end; end; end;

Var (Main)

i, k :Integer;

n :Integer; {Числе исходных точек}

ra :LongInt; {Длина объединения отрезков} begin {Main)

Assignff, Measure.in);

Reset(f); {Файг открыт для чтения}

Read(f,n); {Ввод данных}

for i:=l to n do begin k:=2*i;

Read(f,ab[k-l] ,ab[k] ) ; g[k-l]:=l; {Левая граница} g[k]:=0; {Правая граница}

end;

Close(f);

Assign(f,Measure.out ) ;

открыт для

SortBubble(2*n); Measure(m,2*n);

WriteLn(f,m); {Длина объединения}

Close

end. {Main)

5.5. Последовательный поиск

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

При последовательном поиске подразумевается исследование элементов множества а{, а2,..., ач в том порядке, в котором они встречаются. Начни сначала и продвигайся, пока не найдешь нужный элемент; тогда остановись . Такая последовательная процедура является очевидным способом поиска. Алгоритм 5.7 выполняет последовательный поиск элемента zв множестве а{, а2,..., ап. Несмотря на свою простоту, последовательный поиск содержит ряд очень интересных идей.

Алгоритм Последовательный поиск

с = 0; {Признакпоиска записи z }

f - 1 d f - th \C = for i- on о jz- j enbreak;

ifc= Шеп Запись найдена else Запись не найдена.

Оценим среднюю сложность поиска элементов множества а1% а2,..., а„. Для нахождения /-го элемента at требуется i сравнений. Для вычисления же среднего времени поиска необходимо задать информацию о частоте обращения к каждому элементу множества. Будем предполагать, что частота обращения распределена равномерно, т.е. что ко всем элементам обращаются одинаково часто. Тогда средняя сложность поиска элемента множества

ся-У^ -1 =V(n) линейной. м 2

Рассмотрим распределение частот обращения к элементам в общем случае. Пусть р, обозначает частоту (распределение вероятностей) обращения к элементу аь где р,- > 0 и £Р/ =L В этом

случае средняя сложность (математическое ожидание) поиска

элемента будет равна У/р, . Хорошим приближениемраспределе-(=1

£

ния частот к действительности является закон Зипфа: Р/ =-, для

= 1,2,.. п. (Дж. К. Зипф заметил, что наиболее употребительное в тексте на естественном языке слово встречается с частотой, приблизительно обратно пропорциональной л.) Нормирую-

П

щаяконстанта выбирается так, что £р/ = 1. Пусть элементы множества упорядочены согласно указанным частотам.

5.6. Логарифмический поиск

Логарифмический (бинарный или метод деления пополам) поиск данных применим к сортированному множеству элементов °1 <в2 < *** < ал>размещение которого выполнено на смежной памяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем просто последовательный перебор. Наиболее очевидный метод: начать поиск со среднего элемента, т.е. выполнить сравнение с элементом а,

Результат сравнения позволит определить, в какой половине последовательности tfj, >,..., а, !г .., ап продолжить поиск,

L j J

применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей . Чтобы досконально разобраться в алгоритме, лучше всего представить данные < а2 < ... < ап в виде двоичного

дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево называется деревом сравнений , если для любой его вершины (корня дерева или корня поддерева) выполняется условие:

{Вершим, левого поддерева) <Вершине корня <{ Вершины правого поддерева }.

Тогдас= =1- 1г-исреднеевремяуспешногопоискасо-

А^. Я„ Inn

.С 1 И И + \

ставит ,/j>= /1- -п-с-п - я - ,что много меньше - .

ы\ й #л 1ш 2

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

Алгоритм последовательного поиска данных одинаково эффективно выполняется при размещении множества на

смежной или связанной памяти.

Пусть на очередном шаге деления пополам оказалось, что необходимо выполнить поиск среди элементов я,- < а,+1 <...< щ. В качестве корня принимается элемент a, UJ , где I Щ- ] - наибольшее

целое, меньшее или равное (/+./)/. Левое поддерево располагается в векторе я ai+h..., а. ,ь.. , а правое поддерево - в векторе

[-т\ -1

а\ ,w I ) . На рис. 5.6 показан пример двоичного дерева

L 2 1 ~

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

Рис. 5.6. Пример дерева сравнений, отвечающего бинарному поиску среди сортированных эламитов: 3,5,7,9,12,19,27,44

Поиск элемента z среди < а2 <...< методом деления пополам представлен в алгоритме 5.8.

Аггоритм 5.8. Логарифмический поиск z в < <...<

find 0; {Призна) поиска записи)

= 1; {Лева} граница поддерева) j = и; {Права граница поддерева) while i < jdo begin

. i

т ; {Кореш текущего поддерева)

ifz=am then \(m~ {Элементнайден) m \огеак

else ifz> am then i = m + l {Новаялевая граница) eke j=m - 1 {Новая правая граница) end;

ijfind = 1 then Запись найдена; else Запись отсутствует.

Средняя сложность бинарного поиска среди элементов < <а2 < < й„ сравнима с высотой двоичного дерева (рис 5.6). В худшем случае искомый элемент может оказаться либо на последнем уровне, либо вообще не будет найден. На каждом уровне необходимо выполнить определенное число сравнений. В п.5.4 установлено, что уровней в дереве flog2(n + 1)1. Значит, сложность поиска является логарифмической 0(\og2f0, что оправдывает и название самого метода поиска.

Необходимо отметить, что рассмотренный метод бинарного

поиска предназначен главным образом для сортированных элементов ах < а2 <...< ап на смежной памяти фиксированного п размера. Если же размерность вектора динамически меняется, то экономия от использования бинарного поиска не покроет затрат на поддержание упорядоченного расположения < <... <

5.7. Сортировка с вычисляемыми адресами

Пусть аь а2,..., ап - исходная последовательность сортируемых целых чисел и л = (%ь%2,..., л„) - упорядочивающая перестановка этих элементов ап <аЛ1<... <(ix,. Принятое ограничение, что а, - целые числа, не ведет к потере общности рассматриваемых ниже алгоритмов. Сортированная последовательность

подсказывает очевидный способ использования значений этих

элементов в качестве индексов (адресов) их расположения в массиве bnbr+b...,bs, где Ьа. я, .Получимупорядоченную последовательность <... < а значит, и упорядоченную последовательность исходных данных

В качестве примера рассмотрим частный случай сортировки элементов последовательности %, а2,..., я7, равных соответственно 6, 3, 5, 7, 2, 4, 1 - различные целые числа от 1 до 7. Значение каждого элемента показывает его место в сортированном списке < <... < где определяются в цикле

for 1 to 7 do b , =

Сложность данного метода сортировки является линейной

0(n) где п = 7. Фактически, значения а, определяют перестановку л = (пья2... тсл) =(7,5,2,6,3,1,4), которая упорядочивает элементы Значения устанавливаются в цикле

for to 7donа =/.

5.7. Сортировка с вычисляемыми адресами

Сортировка стала возможной благодаря тому, что значения исходных данных 6, 3, 5, 7, 2, 4, 1 заполняют сплошной интервал последовательности натуральных чисел. Рассмотрим обобщение идеи сортировки с вычисляемыми адресами на случай произвольных целых Л[, 02,..., я . Алгоритм сортировки существенно упрощается, если все значения различные.

Значения я я,..... я. - различные

Реализация метода сортировки представлена в алгоритме 5.9. Временный массив br, b,.,., bs, где r=min(fl1, аъ..., я ) и s = используется для сортированной упаковки

элементов аь а2,..., ап. Свободные места в массиве bn brtl,..., b. инициализируются значением s + 1, отличным от значений элементов flj, #1,.,., ап-

Алгоритм 5.9. Сортировка с вычисляемыми адресами для различных ah а2,.-., а„

{Поисктт и max значений среди аь а2,..., ап } r s =ci}:

for i = 2 ton do begin ifr> a,then r= a, else ifs< я, then s = at end;

{ИнициализацияЬ, значением s+l, отличным от a, } fori = rtosdobs+ 1; {Сортированна.упаковка элементов a{, a2,.., an } fori= 1 ton doba. =at;

{Выделение сортированных а j, a2,..., an из bn Ь^л,..., bs } k = 0;

for i = rto s do begin ifbj*s+l then begin k = k+l;

end; end.

Сортированный вектор а у < a2 <...< an является результатом

последовательного просмотра массива/?,./ ].....bs при удалении

из него оставшихся незанятыми элементов, равных значению