Сортировки включением

СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа-

лизации стратегии включения. Порядок алгоритма сортировки просты-

ми вставками - O(N^2), если учитывать только операции сравнения.

Но сортировка требует еще и в среднем N^2/4 перемещений, что де-

лает ее в таком варианте значительно менее эффективной, чем сор-

тировка выборкой.

Алгоритм сортировки простыми вставками иллюстрируется прог-

раммным примером 3.11.

{===== Программный пример 3.11 =====}

Procedure Sort(a : Seq; var b : Seq);

Var i, j, k : integer;

begin

for i:=1 to N do { перебор входного массива }

{ поиск места для a[i] в выходном массиве }

begin j:=1; while (j<i) and (b[j]<=a[i]) do j:=j+1;

{ освобождение места для нового эл-та }

for k:=i downto j+1 do b[k]:=b[k-1];

b[j]:=a[i]; { запись в выходной массив }

end; end;

Эффективность алгоритма может быть несколько улучшена при

применении не линейного, а дихотомического поиска. Однако, следу-

ет иметь в виду, что такое увеличение эффективности может быть

достигнуто только на множествах значительного по количеству эле-

ментов объема. Но поскольку алгоритм требует большого числа пере-

сылок, то при значительном объеме одной записи эффективность мо-

жет определяться не количеством операций сравнения, а количеством

пересылок. Алгоритм обменной сортировки простыми вставками отли-

чается от базового алгоритма только тем, что входное и выходное

множество будут разделять одну область памяти.

ПУЗЫРЬКОВАЯ СОРТИРОВКА ВСТАВКАМИ. Это модификация обменного

варианта сортировки. При такой сортировке входное и выходное мно-

жества находятся в одной последовательности, причем выходное - в

начальной ее части. В исходном состоянии можно считать, что пер-

вый элемент последовательности уже принадлежит упорядоченному вы-

ходному множеству, остальная часть последовательности - неупоря-

доченное входное. Первый элемент входного множества примыкает к

концу выходного множества. На каждом шаге сортировки происходит

перераспределение последовательности: выходное множество увеличи-

вается на один элемент, а входное - уменьшается. Это происходит

за счет того, что первый элемент входного множества теперь счита-

ется последним элементом выходного. Затем выполняется просмотр

выходного множества от конца к началу с перестановкой соседних

элементов, которые не соответствуют критерию упорядоченности.

Просмотр прекращается, когда прекращаются перестановки. Это при-

водит к тому, что последний элемент выходного множества "выплыва-

ет" на свое место в множестве. Поскольку при этом перестановка

приводит к сдвигу нового в выходном множестве элемента на одну

позицию влево, нет смысла всякий раз производить полный обмен

между соседними элементами - достаточно сдвигать старый элемент

вправо, а новый элемент записать в выходное множество, когда его

место будет установлено. Именно так и построен программный пример

пузырьковой сортировки вставками - 3.12.

{===== Программный пример 3.12 =====}

Procedure Sort (var a : Seq);

Var i, j, k, t : integer;

begin for i:=2 to N do { перебор входного массива }

{*** вх.множество - [i..N], вых.множество - [1..i] }

begin t:=a[i]; { запоминается значение нового эл-та }

j:=i-1; {поиск места для эл. в вых. множестве со сдвигом}

{конец цикла при достижении начала или, если найден эл.меньший

нового} while (j>=1) and (a[j]>t) do

begin a[j+1]:=a[j]; { все эл-ты, большие нового сдвигаются }

j:=j-1; { цикл от конца к началу выходного множества }

end; a[j+1]:=t; { новый эл-т ставится на свое место }

end; end;

Результаты трассировки программного примера 3.12 представле-

ны в таблице 3.8.

Таблица 3.8

┌─────────┬───────────────────────────────┐

│ шаг │ содержимое массива a │

├─────────┼───────────────────────────────┤

│исходный │ 48:43 90 39 9 56 40 41 75 72 │

│ 1 │ 43 48:90 39 9 56 40 41 75 72 │

│ 2 │ 43 48 90:39 9 56 40 41 75 72 │

│ 3 │ 39 43 48 90: 9 56 40 41 75 72 │

│ 4 │ 9 39 43 48 90:56 40 41 75 72 │

│ 5 │ 9 39 43 48 56 90:40 41 75 72 │

│ 6 │ 9 39 40 43 48 56 90:41 75 72 │

│ 7 │ 9 39 40 41 43 48 56 90:75 72 │

│ 8 │ 9 39 40 41 43 48 56 75 90:72 │

│результат│ 9 39 40 41 43 48 56 72 75 90:│

└─────────┴───────────────────────────────┘

Хотя обменные алгоритмы стратегии включения и позволяют сок-

ратить число сравнений при наличии некоторой исходной упорядочен-

ности входного множества, значительное число пересылок существен-

но снижает эффективность этих алгоритмов. Поэтому алгоритмы

включения целесообразно применять к связным структурам данных,

когда операция перестановки элементов структуры требует не пере-

сылки данных в памяти, а выполняется способом коррекции указате-

лей (см. главу 5).

Еще одна группа включающих алгоритмов сортировки использует

структуру дерева. Рассмотрение последующих алгоритмов будет по-

лезно после ознакомления с главой 6.

СОРТИРОВКА УПОРЯДОЧЕННЫМ ДВОИЧНЫМ ДЕРЕВОМ. Алгоритм склады-

вается из построения упорядоченного двоичного дерева и последую-

щего его обхода. Если нет необходимости в построении всего линей-

ного упорядоченного списка значений, то нет необходимости и в об-

ходе дерева, в этом случае применяется поиск в упорядоченном дво-

ичном дереве. Алгоритмы работы с упорядоченными двоичными деревь-

ями подробно рассмотрены в главе 6. Отметим, что порядок алгорит-

ма - O(N*log2(N)), но в конкретных случаях все зависит от упоря-

доченности исходной последовательности, который влияет на степень

сбалансированности дерева и в конечном счете - на эффективность

поиска.

ТУРНИРНАЯ СОРТИРОВКА. Этот метод сортировки получил свое

название из-за сходства с кубковой системой проведения спортивных

соревнований: участники соревнований разбиваются на пары, в кото-

рых разыгрывается первый тур; из победителей первого тура состав-

ляются пары для розыгрыша второго тура и т.д. Алгоритм сортировки

состоит из двух этапов. На первом этапе строится дерево: анало-

гичное схеме розыгрыша кубка.

Например, для последовательности чисел: 16 21 8 14 26 94 30 1

такое дерево будет иметь вид пирамиды, показанной на рис. 3.13. 1

┌───────┴───────┐

8 1

┌───┴───┐ ┌───┴───┐

16 8 26 1

┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐

16 21 8 14 26 94 30 1

 

Рис.3.13. Пирамида турнирной сортировки

В примере 3.13 приведена программная иллюстрация алгоритма

турнирной сортировки. Она нуждается в некоторых пояснениях.

Построение пирамиды выполняется функцией Create_Heap. Пирамида

строится от основания к вершине. Элементы, составляющие каждый

уровень, связываются в линейный список, поэтому каждый узел дере-

ва помимо обычных указателей на потомков - left и right - содер-

жит и указатель на "брата" - next. При работе с каждым уровнем

указатель содержит начальный адрес списка элементов в данном

уровне. В первой фазе строится линейный список для нижнего уровня

пирамиды, в элементы которого заносятся ключи из исходной после-

довательности. Следующий цикл while в каждой своей итерации надс-

траивает следующий уровень пирамиды. Условием завершения этого

цикла является получение списка, состоящего из единственного эле-

мента, то есть, вершины пирамиды. Построение очередного уровня

состоит в попарном переборе элементов списка, составляющего пре-

дыдущий (нижний) уровень. В новый уровень переносится наименьшее

значение ключа из каждой пары.

Следующий этап состоит в выборке значений из пирамиды и фор-

мирования из них упорядоченной последовательности (процедура

Heap_Sort и функция Competit). В каждой итерации цикла процедуры

Heap_Sort выбирается значение из вершины пирамиды - это наимень-

шее из имеющихся в пирамиде значений ключа. Узел-вершина при этом

освобождается, освобождаются также и все узлы, занимаемые выбран-

ным значением на более низких уровнях пирамиды. За освободившиеся

узлы устраивается (снизу вверх) состязание между их потомками.

Так, для пирамиды, исходное состояние которой было показано на

рис 3.13, при выборке первых трех ключей (1, 8, 14) пирамида бу-

дет последовательно принимать вид, показанный на рис.3.14 (симво-

лом x помечены пустые места в пирамиде).

8 14 16

┌─────┴────┐ ┌───┴────┐ ┌───┴──┐

8 26 14 26 16 26

┌──┴──┐ ┌──┴─┐ ┌─┴─┐ ┌──┴─┐ │ ┌─┴─┐

16 8 26 30 16 14 26 30 16 26 30

┌─┴┐ ┌─┴┐ ┌┴─┐ │ ┌─┴┐ │ ┌┴─┐ │ ┌─┴┐ ┌┴─┐ │

16 21 8 14 26 94 30 16 21 14 26 94 30 16 21 26 94 30

а). выбрано число 1 б). выбрано число 8 в). выбрано число 14

Рис.3.14. Пирамида после последовательных выборок

Процедура Heap_Sort получает входной параметр ph - указатель

на вершину пирамиды и формирует выходной параметр a - упорядочен-

ный массив чисел. Вся процедура Heap_Sort состоит из цикла, в

каждой итерации которого значение из вершины переносится в массив

a, а затем вызывается функция Competit, которая обеспечивает ре-

организацию пирамиды в связи с удалением значения из вершины.

Функция Competet рекурсивная, ее параметром является указа-

тель на вершину того поддерева, которое подлежит реорганизации. В

первой фазе функции устанавливается, есть ли у узла, составляюще-

го вершину заданного поддерева, потомок, значение данных в кото-

ром совпадает со значением данных в вершине. Если такой потомок

есть, то функция Competit вызывает сама себя для реорганизации

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

После реорганизации адрес потомка в узле заменяется тем адресом,

который вернул рекурсивный вызов Competit. Если после реорганиза-

ции оказывается, что у узла нет потомков (или он не имел потомков

с самого начала), то узел уничтожается и функция возвращает пус-

той указатель. Если же у узла еще остаются потомки, то в поле

данных узла заносится значение данных из того потомка, в котором

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

{===== Программный пример 3.13 =====}

{ Турнирная сортировка }

type nptr = ^node; { указатель на узел }

node = record { узел дерева }

key : integer; { данные }

left, right : nptr; { указатели на потомков }

next : nptr; { указатель на "брата" }

end;

{ Создание дерева - функция возвращает указатель на вершину

созданного дерева }

Function Heap_Create(a : Seq) : nptr;

var i : integer;

ph2 : nptr; { адрес начала списка уровня }

p1 : nptr; { адрес нового элемента }

p2 : nptr; { адрес предыдущего элемента }

pp1, pp2 : nptr; { адреса соревнующейся пары }

begin

ph2:=nil; {Фаза 1- построение самого нижнего уровня пирамиды}

for i:=1 to n do

begin New(p1); { выделение памяти для нового эл-та }

p1^.key:=a[i]; { запись данных из массива }

p1^.left:=nil; p1^.right:=nil; { потомков нет }

{ связывание в линейный список по уровню }

if ph2=nil then ph2:=p1 else p2^.next:=p1; p2:=p1;

end; { for } p1^.next:=nil;

{ Фаза 2 - построение других уровней }

while ph2^.next<>nil do { цикл до вершины пирамиды }

begin pp1:=ph2; ph2:=nil; { начало нового уровня }

while pp1<>nil do { цикл по очередному уровню}

begin pp2:=pp1^.next; New(p1);

{ адреса потомков из предыдущего уровня }

p1^.left:=pp1; p1^.right:=pp2; p1^.next:=nil;

{ связывание в линейный список по уровню }

if ph2=nil then ph2:=p1 else p2^.next:=p1; p2:=p1;

{ состязание данных за выход на уровень }

if (pp2=nil)or(pp2^.key>pp1^.key) then p1^.key:=pp1^.key

else p1^.key:=pp2^.key; { переход к следующей паре }

if pp2<>nil then pp1:=pp2^.next else pp1:=nil;

end; { while pp1<>nil }

end; { while ph2^.next<>nil }

Heap_Create:=ph2; end;

{ Реорганизация поддерева - функция возвращает указатель на

вершину реорганизованного дерева }

Function Competit(ph : nptr) : nptr;

begin

{ определение наличия потомков, выбор потомка для

реорганизации, реорганизация его }

if (ph^.left<>nil)and(ph^.left^.key=ph^.key) then

ph^.left:=Competit(ph^.left)

else if (ph^.right<>nil) then

ph^.right:=Competit(ph^.right);

if (ph^.left=nil)and(ph^.right=nil) then

{ освобождение пустого узла }

begin Dispose(ph); ph:=nil; end;

else { состязание данных потомков }

if (ph^.left=nil) or

((ph^.right<>nil)and(ph^.left^.key>ph^.right^.key)) then

ph^.key:=ph^.right^.key

else ph^.key:=ph^.left^.key;

Competit:=ph; end;

Procedure Heap_Sort(var a : Seq); { Сортировка }

var ph : nptr; { адрес вершины дерева }

i : integer;

begin

ph:=Heap_Create(a); { создание дерева }

for i:=1 to N do { выборка из дерева }

begin a[i]:=ph^.key; { перенос данных из вершины в массив }

ph:=Competit(ph); { реорганизация дерева }

end; end;

Построение дерева требует N-1 сравнений, выборка - N*log2(N)

сравнений. Порядок алгоритма, таким образом, O(N*log2(N)). Слож-

ность операций над связными структурами данных, однако, значи-

тельно выше, чем над статическими структурами. Кроме того, алго-

ритм неэкономичен в отношении памяти: дублирование данных на

разных уровнях пирамиды приводит к тому, что рабочая область па-

мяти содержит примерно 2*N узлов.

СОРТИРОВКА ЧАСТИЧНО УПОРЯДОЧЕННЫМ ДЕРЕВОМ. В двоичном дере-

ве, которое строится в этом методе сортировки для каждого узла

справедливо следующее утверждение: значения ключа, записанное в

узле, меньше, чем ключи его потомков. Для полностью упорядоченно-

го дерева имеются требования к соотношению между ключами потом-

ков. Для данного дерева таких требований нет, поэтому такое дере-

во и называется частично упорядоченным. Кроме того, дерево должно

быть абсолютно сбалансированным. Это означает не только то, что

длины путей к любым двум листьям различаются не более, чем на 1,

но и то, что при добавлении нового элемента в дерево предпочтение

всегда отдается левой ветви/подветви, пока это не нарушает сба-

лансированность. Более подробно деревья рассматриваются в гл.6.

Например, последовательность чисел: 3 20 12 58 35 30 32 28

будет представлена в виде дерева, показанного на рис. 3.15.

┌───────┴───────┐

20 12

┌───┴───┐ ┌───┴───┐

28 35 30 32

┌─┘

58 *

Рис.3.15. Частично упорядоченное дерево

Представление дерева в виде пирамиды наглядно показывает,

что для такого дерева можно ввести понятия "начала" и "конца".

Началом, естественно, будет считаться вершина пирамиды, а концом

- крайний левый элемент в самом нижнем ряду (на рис.3.15 это 58).

Для сортировки этим методом должны быть определены две опе-

рации: вставка в дерево нового элемента и выборка из дерева мини-

мального элемента; причем выполнение любой из этих операций не

должно нарушать ни сформулированной выше частичной упорядоченнос-

ти дерева, ни его сбалансированности.

Алгоритм вставки состоит в следующем. Новый элемент вставля-

ется на первое свободное место за концом дерева (на рис.3.15 это

место обозначено символом "*"). Если ключ вставленного элемента

меньше, чем ключ его предка, то предок и вставленный элемент ме-

няются местами. Ключ вставленного элемента теперь сравнивается с

ключом его предка на новом месте и т.д. Сравнения заканчиваются,

когда ключ нового элемента окажется больше ключа предка или когда

новый элемент "выплывет" в вершину пирамиды. Пирамида, показанная

на рис.3.15, построена именно последовательным включением в нее

чисел из приведенного ряда. Если мы включим в нее, например, еще

число 16, то пирамида примет вид, представленный на рис.3.16.

(Символом "*" помечены элементы, перемещенные при этой операции.)

┌───────┴───────┐

16* 12

┌───┴───┐ ┌───┴───┐

20* 35 30 32

┌─┴─┐

58 28*

Рис.3.16. Частично упорядоченное дерево, включение элемента

Процедура выборки элемента несколько сложнее. Очевидно, что

минимальный элемент находится в вершине. После выборки за освобо-

дившееся место устраивается состязание между потомками, и в вер-

шину перемещается потомок с наименьшим значением ключа. За осво-

бодившееся место перемешенного потомка состязаются его потомки и

т.д., пока свободное место не опустится до листа пирамиды. Состо-

яние дерева после выборки из него минимального числа (3) показано

на рис.3.17. а).

 

12* 12

┌───────┴───────┐ ┌───────┴───────┐

16 30* 16 28*

┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐

20 35 * 32 20 35 30* 32

┌─┴─┐ ┌─┴─┐

58 28 58 *

а). исключение б). балансирование

Рис.3.17. Частично упорядоченное дерево, исключение элемента

Упорядоченность дерева восстановлена, но нарушено условие

его сбалансированности, так как свободное место находится не в

конце дерева. Для восстановления сбалансированности последний

элемент дерева переносится на освободившееся место, а затем

"всплывает" по тому же алгоритму, который применялся при вставке.

Результат такой балансировки показан на рис.3.17.б.

Прежде, чем описывать программный пример, иллюстрирующий

сортировку частично упорядоченным деревом - пример 3.14, рассмот-

рим способ представления дерева в памяти. Это способ представле-

ния двоичных деревьев в статической памяти (в одномерном масси-

ве), который может быть применен и в других задачах. Элементы де-

рева располагаются в соседних слотах памяти по уровням. Самый

первый слот выделенной памяти занимает вершина. Следующие 2 слота

- элементы второго уровня, следующие 4 слота - третьего и т.д.

Дерево с рис.3.17.б, например, будет линеаризовано таким образом:

12 16 28 20 35 30 32 58

В таком представлении отпадает необходимость хранить в составе

узла дерева указатели, так как адреса потомков могут быть вычис-

лены. Для узла, представленного элементом массива с индексом i

индексы его левого и правого потомков будут 2*i и 2*i+1 соответс-

твенно. Для узла с индексом i индекс его предка будет i div 2.

После всего вышесказанного алгоритм программного примера

3.14 не нуждается в особых пояснениях. Поясним только структуру

примера. Пример оформлен в виде законченного программного модуля,

который будет использован и в следующем примере. Само дерево

представлено в массиве tree, переменная nt является индексом пер-

вого свободного элемента в массиве. Входные точки модуля:

- процедура InitST - инициализация модуля, установка начального

значения nt;

- функция InsertST - вставка в дерево нового элемента; функция

возвращает false, если в дереве нет свободного места, иначе -

true;

- функция DeleteST - выборка из дерева минимального элемента;

функция возвращает false, если дерево пустое, иначе - true;

- функция CheckST - проверка состояния дерева: ключ минимального

элемента возвращается в выходном параметре, но элемент не иск-

лючается из дерева; а возвращаемое значение функции - 0 - если

дерево пустое, 1 - если дерево заполнено не до конца, 2 - если

дерево заполнено до конца.

Кроме того в модуле определены внутренние программные едини-

цы:

- функция Down - обеспечивает спуск свободного места из вершины

пирамиды в ее основание, функция возвращает индекс свободного

места после спуска; - процедура Up - обеспечивающая всплытие

элемента с заданного места.

{===== Программный пример 3.14 =====}

Unit SortTree; { Сортировка частично упорядоченным деревом }

Interface

Procedure InitSt;

Function CheckST(var a : integer) : integer;

Function DeleteST(var a : integer) : boolean;

Function InsertST(a : integer) : boolean;

Implementation

Const NN=16;

var tr : array[1..NN] of integer; { дерево }

nt : integer; { индекс последнего эл-та в дереве }

Procedure Up(l : integer); {Всплытие эл-та с места с индексом l}

var h : integer; {l - индекс узла, h - индекс его предка}

x : integer;

begin h:=l div 2; { индекс предка }

while h>0 do { до начала дерева }

if tr[l]<tr[h] then { ключ узла меньше, чем у предка }

begin x:=tr[l]; tr[l]:=tr[h]; tr[h]:=x; { перестановка }

l:=h; h:=l div 2; { предок становится текущим узлом }

end else h:=0; { конец всплытия }

end; { Procedure Up }

{** Спуск свободного места из начала дерева **}

Function Down : integer;

var h, l : integer; { h - индекс узла, l - индекс его потомка}

begin h:=1; { начальный узел - начало дерева }

while true do

begin l:=h*2; { вычисление индекса 1-го потомка }

if l+1<=nt then { у узла есть 2-й потомок }

begin if tr[l]<=tr[l+1] then { 1-й потомок меньше 2-го }

begin tr[h]:=tr[l]; {1-й потомок переносится в тек. узел}

h:=l; end { 1-й потомок становится текущим узлом }

else { 2-й потомок меньше 1-го }

begin tr[h]:=tr[l+1]; {2-й потомок переносится в текущ.узел}

h:=l+1; end; {2-й потомок становится текущим узлом}

end else

if l=nt then { 1-й потомок есть, 2-го нет }

begin tr[h]:=tr[l]; {1-й потомок переносится в текущ.узел}

Down:=l; Exit; { спуск закончен }

end else { потомков нет - спуск закончен }

begin Down:=h; Exit; end;

end; { while }

end; { Function Down }

Procedure InitSt; {** Инициализация сортировки деревом **}

begin nt:=0; { дерево пустое }

end; { Procedure InitSt }

{** Проверка состояния дерева **}

Function CheckST(var a : integer) : integer;

begin a:=tr[1]; { выборка эл-та из начала }

case nt of { формирование возвращаемого значения функции }

0: { дерево пустое } CheckSt:=0;

NN: { дерево полное } CheckSt:=2;

else { дерево частично заполнено } CheckSt:=1;

end;

end; { Function CheckST }

{** Вставка эл-та a в дерево **}

Function InsertST(a : integer) : boolean;

begin

if nt=NN then { дерево заполнено - отказ }

InsertST:=false else { в дереве есть место }

begin nt:=nt+1; tr[nt]:=a; { запись в конец дерева }

Up(nt); InsertSt:=true; { всплытие }

end; end; { Function InsertST }

{** Выборка эл-та из дерева **}

Function DeleteST(var a : integer) : boolean;

var n : integer;

begin

if nt=0 then { дерево пустое - отказ }

DeleteST:=false else { дерево не пустое }

begin a:=tr[1]; { выборка эл-та из начала }

n:=Down; { спуск свободного места в позицию n }

if n<nt then begin

{ если свободное место спустилось не в конец дерева }

tr[n]:=tr[nt]; { эл-т из конца переносится на своб.место }

Up(n); end; { всплытие }

nt:=nt-1; DeleteSt:=true;

end; end; { Function DeleteST }

END.

Если применять сортировку частично упорядоченным деревом для

упорядочения уже готовой последовательности размером N, то необ-

ходимо N раз выполнить вставку, а затем N раз - выборку. Порядок

алгоритма - O(N*log2(N)), но среднее значение количества сравне-

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

сортировка частично упорядоченным деревом имеет одно существенное

преимущество перед всеми другими алгоритмами. Дело в том, что это

самый удобный алгоритм для "сортировки on-line", когда сортируе-

мая последовательность не зафиксирована до начала сортировки, а

меняется в процессе работы и вставки чередуются с выборками. Каж-

дое изменение (добавление/удаление элемента) сортируемой последо-

вательности потребует здесь не более, чем 2*log2(N) сравнений и

перестановок, в то время, как другие алгоритмы потребуют при еди-

ничном изменении переупорядочивания всей последовательности "по

полной программе".

Типичная задача, которая требует такой сортировки, возникает

при сортировке данных на внешней памяти (файлов). Первым этапом

такой сортировки является формирование из данных файла упорядо-

ченных последовательностей максимально возможной длины при огра-

ниченном объеме оперативной памяти. Приведенный ниже программный

пример (пример 3.15) показывает решение этой задачи.

Последовательность чисел, записанная во входном файле поэле-

ментно считывается и числа по мере считывания включаются в дере-

во. Когда дерево оказывается заполненным, очередное считанное из

файла число сравнивается с последним числом, выведенным в выход-

ной файл. Если считанное число не меньше последнего выведенного,

но меньше числа, находящегося в вершине дерева, то в выходной

файл выводится считанное число. Если считанное число не меньше

последнего выведенного, и не меньше числа, находящегося в вершине

дерева, то в выходной файл выводится число, выбираемое из дерево,

а считанное число заносится в дерево. Наконец, если считанное

число меньше последнего выведенного, то поэлементно выбирается и

выводится все содержимое дерева, и формирование новой последова-

тельности начинается с записи в пустое дерево считанного числа.

{===== Программный пример 3.15 =====}

{ Формирование отсортированных последовательностей в файле }

Uses SortTree;

var x : integar; { считанное число }

y : integer; { число в вершине дерева }

old : integer; { последнее выведенное число }

inp : text; { входной файл }

out : text; { выходной файл }

bf : boolean; { признак начала вывода последовательности }

bx : boolean; { рабочая переменная }

begin

Assign(inp,'STX.INP'); Reset(inp);

Assign(out,'STX.OUT'); Rewrite(out);

InitST; { инициализация сортировки }

bf:=false; { вывод последовательности еще не начат }

while not Eof(inp) do

begin ReadLn(inp,x); { считывание числа из файла }

{ если в дереве есть свободное место - включить в дерево }

if CheckST(y)<=1 then bx:=InsertST(x)

else { в дереве нет свободного места }

if (bf and (x<old)) or (not bf and (x<y)) then

{ вывод содержимого дерева }

begin while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out);

bf:=false; { начало новой последовательности }

bx:=InsertST(x); { занесение считанного числа в дерево }

end else { продолжение формирования последовательности }

begin if x<y then { вывод считанного числа }

begin Write(out,x:3,' '); old:=x; end;

else { вывод числа из вершины дерева }

begin bx:=DeleteST(y);

Write(out,y:3,' '); old:=y;

bx:=InsertST(x); { занесение считанного в дерево }

end; bf:=true; { вывод последовательности начался }

end; end;

Close(inp); { вывод остатка }

while DeleteST(y) do Write(out,y:3,' ');

WriteLn(out); Close(out);

end.