Внешняя сортировка

Begin

Repeat

Begin

Begin

Begin

Begin

Repeat

Begin

Вegin

End

Begin

Begin

End

Begin

End

Else break;

End;

End;

11.2.2 Сортировка бинарными включениями

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[0],..., a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти быстрее, применив бинарный поиск, который определяет срединный элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями, он показан в следующей программе:

Рrocedure BinInsSort;

Var i, j, L, R, m: Integer;

x: TElement;

For i:=2 To N Do Begin

x:= a[i-1]; L:= 1; R:= i-1;

While L <= R Do Begin

m:= (L + R) Div 2;

If x.Кey < a[m-1].Кey Then R:= m - 1

Else L:= m + 1;

End;

For j:= i-1 Downto L Do a[j]:= a[j-1];

a[l-1]:= x;

End;

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

11.2.3 Сортировка прямым выбором

Этот метод основан на следующем алгоритме:

- выбираем (выделяем) элемент с наименьшим (среди всех N элементов) ключом, допустим это элемент a[k]:

a[k].Key = min(a[0].Key, a[1].Key, …, a[HighIndex].Key)

- элемент a[k] меняется местами с первым элементом, т. е. с элементом a[0].

Затем выбираем элемент с наименьшим ключом среди всех элементов, кроме элемента a[0]; меняем его местами с элементом a[1] и т. д.

Эти операции затем повторяются с оставшимися N-2 элементами, затем с N-3 элементами, пока не останется только один элемент - наибольший. Метод, основанный на принципе пошагового выбора, продемонстрирован на тех же восьми ключах:

Обобщенно алгоритм прямого выбора можно представить следующим образом:

For i:=0 To HighIndex Do

<присвоить k индекс

наименьшего элемента из a[i], … a[HighIndex]>;

<поменять местами a[i] и a[k]>;

end;

Этот метод, называемый сортировкой прямым (простым) выбором, в некотором смысле противоположен сортировке простыми включениями; при сортировке простыми включениями на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готового массива для нахождения места для включения; при сортировке простым выбором рассматриваются все элементы входного массива для нахождения элемента с наименьшим ключом, и этот один очередной элемент отправляется в готовую последовательность.

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

Весь алгоритм сортировки простым выбором реализован в следующей программе DirSelSort:

Рrocedure DirSelSort;

Var i, j, k: Integer;

x: TElement;

For i:=0 To HighIndex-1 Do Begin

x:=a[i]; k:= i;

For j:=i+1 To HighIndex Do

If x.Key > a[j].Key Then Begin

k:=j; x:=a[j];

End;

a[k]:=a[i]; a[i]:=x;

End;

11.2.4 Сортировка прямым обменом

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

Если мы будем рассматривать массив, расположенный вертикально, а не горизонтально, и представим себе элементы пузырьками в резервуаре с водой, обладающими «весами», соответствующими их ключам, то каждый проход по массиву приводит к «всплыванию» пузырька на соответствующий его весу уровень. Этот метод широко известен как сортировка методомпузырька или пузырьковой сортировкой.

Проход метода начинается с конца сортируемого массива. Ключ последнего элемента a[HighIndex] сравнивается с ключом предпоследнего элемента a[HighIndex-1]. Если

a[HighIndex].Key < a[HighIndex-1].Key,

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

Алгоритм пузырьковой сортировки иллюстрируется результатами выполнения проходов на тех же, что и ранее, ключах:

Простейшей реализацией пузырьковой сортировки является подпрограмма BubbleSort, показанная ниже:

Рrocedure BubbleSort;

Var i, j: Integer;

x: TElement;

flag: boolean;

For i:= 1 To HighIndex Do Begin

// Начало прохода

flag:= True;

For j:= HighIndex DownTo i Do

If a[j-1].Key > a[j].Key Then Begin

flag:= False;

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x

end;

// Если обменов не было, то закончить

If flag Then Break;

End;

End;

В подпрограмме BubbleSort используется булева переменная flag, которая устанавливается в True в начале каждого прохода. Если при выполнении очередного прохода не было выполнено ни одного обмена, это означает, что массив a упорядочен. В этом случае переменная flag не изменяет своего значения и происходит выход из подпрограммы BubbleSort.

Внимательный читатель заметит здесь странную асимметрию: самый «легкий пузырек», расположенный в «тяжелом» конце неупорядоченного массива всплывет на нужное место за один проход, а «тяжелый пузырек», неправильно расположенный в «легком» конце будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив

12, 18, 42, 44, 55, 67, 94, 06

будет рассортирован при помощи метода пузырька за один проход, а сортировка массива

94, 06, 12, 18, 42, 44, 55, 67

требует семи проходов, пока ключ 94 не окажется в конце массива. Эта неестественная асимметрия подсказывает следующее улучшение: менять направление следующих один за другим проходов. Полученный в результате алгоритм называют шейкер-сортировкой. Его работа показана на следующем примере:

Из рисунка видно, что в результате первого прохода наверх переместился самый «легкий» ключ 06. А самый «тяжелый элемент», имеющий ключ 94, переместился на свое место уже на втором проходе, чего не наблюдалось при рассмотрении пузырьковой сортировки.

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

Можно показать, что среднее расстояние, на которое должен переместиться каждый из N элементов во время сортировки, - это N/3 мест. Это число дает ключ к поиску усовершенствованных, т. е. более эффективных, методов сортировки. Все простые методы в принципе перемещают каждый элемент на одну позицию на каждом элементарном шаге. Поэтому они требуют порядка N² таких шагов. Любое улучшение должно основываться на принципе пересылки элементов за один шаг на большое расстояние.

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

Procedure ShakerSort;

Var j, k,L,R: Integer;

x: TElement;

flag: boolean;

L:=1; R:= HighIndex; k:= R;

flag:= true;

For j:=R DownTo L Do Begin

If a[j-1].Key > a[j].Key Then Begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;

k:=j; flag:= false;

end;

End;

If flag Then Break;

L:=k+1;

flag:= True;

For j:=L To R Do

If a[j-1].Key > a[j].Key Then Begin

x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;

k:=j; flag:= false;

end;

If flag Then Break;

R:=k-1;

Until L > R

End;

11.2.5 Сортировка методом Шелла

Некоторое усовершенствование сортировки простыми включениями было предложено Д. Л. Шеллом в 1959 году. Этот метод показан на следующем примере.

Сортировка с убывающими расстояниями:

Расстоянием h между двумя элементами a[j] и a[i] называется положительная разность их индексов. Например, расстояние между элементами a[2] и a[6] равно 4 (h = 6-2).

На первом проходе отдельно группируются и сортируются (внутри группы) методом простого включения все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В нашем примере из восьми элементов каждая группа на первом проходе содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, расстояние между которыми равно 2, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец на третьем проходе все элементы сортируются обычной сортировкой включением (1-сортировка). Заметим, что группы, в которых последовательные элементы отстоят на одинаковые расстояния, никуда не передаются - они остаются «на том же месте».

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

Очевидно, что этот метод дает упорядоченный массив, и что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей (2×i)-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки.

Все t приращений обозначим через h₁, h₂,..., h_t с условиями

h_t = 1, h_i+1 < h_i, i=1, …, t-1.

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

Программа сортировки методом Шелла может иметь следующий вид:

Procedure ShellSort;

Var i, j, k, t, m: integer;

x: TElement;

h: Array [1..20] Of integer;

t:= Round(Ln(N)/Ln(3))-1;

If t = 0 Then t:= 1;

h[t]:= 1;

For m:= t-1 Downto 1 Do

h[m]:= 3*h[m+1] + 1;

For m:= 1 To t Do Begin

k:= h[m];

For i:= k+1 To N Do Begin

j:= i - k;

While a[j+k-1].Key < a[j-1].Key Do Begin

x:= a[j+k-1];

a[j+k-1]:= a[j-1];

a[j-1]:= x;

j:= j - k;

If j < 1 Then Break;

End {While}

End; {For i}

End; {For m}

End;

В литературе рекомендуется такая последовательность приращений (записанная в обратном порядке):

1, 4, 13, 40, 121,...,

где h_i-1= 3h_i+1, h_t= 1 и t= log₃(N-1). Именно такие параметры задаются в подпрограмме ShellSort. Приемлемой считается также последовательность

1, 3, 7, 15, 31,...,

где h_i-1= 2h_i+1, и t= log₂(N-1). Анализ показывает, что в последнем случае затраты, которые требуются для сортировки Nэлементов с помощью алгоритма сортировки Шелла, пропорциональны N ^1,2.

11.2.6 Сортировка с помощью бинарного дерева

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди Nэлементов, затем среди N-1 элементов и т. д. Понятно, что поиск наименьшего ключа из Nэлементов требует N-1 сравнений, а поиск его среди N-1 элементов - еще N-2 сравнений.

Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью N/2 сравнений можно определить наименьший ключ из каждой пары. При помощи следующих N/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего N-1 сравнений мы можем построить дерево выбора, как показано на рисунке 11.1, и определить корень, как наименьший ключ.

Рисунок 11.1 - Построение дерева при последовательном выборе из двух ключей

На втором шаге выполняется спуск по пути, отмеченном наименьшим ключом, с последовательной заменой его на «дыру» (или ключ-бесконечность). По достижении (при спуске) элемента-листа, соответствующего наименьшему ключу, этот элемент исключается из дерева и помещается в начало некоторого списка. Результат выполнения этого процесса показан на рисунке 11.2.

Рисунок 11.2 - Спуск по дереву с образованием дыр и формирование
упорядоченного списка из исключаемых элементов

Затем происходит заполнение элементов-«дыр» в направлении снизу вверх. При этом очередной заполняемый пустой элемент («дыра») получает значение ключа, наименьшего среди значений сыновей этого элемента. В результате получается дерево, изображенное на рисунке 11.3.

Рисунок 11.3 - Заполнение «дыр»

Элемент, который оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся элементов и может быть исключен из дерева и включен в «готовую» последовательность. После N таких шагов дерево становится пустым (т. е. состоит из «дыр»), и процесс сортировки завершается.

При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов; в конечном счете, для хранения возросшего объема информации нужно строить некую древовидную структуру. Также желательно избавиться от необходимости в «дырах», которые в конце заполняют дерево и приводят к большому числу ненужных сравнений. Кроме того, нужно найти способ представить дерево из Nэлементов в N единицах памяти вместо 2N-1 единиц. Это можно осуществить с помощью метода, который его изобретатель Дж. Уильямс назвал пирамидальной сортировкой.

11.2.7 Пирамидальная сортировка

Пирамида определяется как некоторая последовательность ключей

K[L], …, K[R],

такая, что

K[i] £ K[2i] & K[i] £ K[2i+1], (11.1)

для всякого i = L, …, R/2. Если имеется массив K[1], K[2], …, K[R], который индексируется от 1, то этот массив можно представить в виде двоичного дерева. Пример такого представления при R=10 показан на рисунке 11.4.

Рисунок 11.4 - Массив ключей, представленный в виде двоичного дерева

Дерево, изображенное на рисунке 11.4, представляет собой пирамиду, поскольку для каждого i = 1, 2, …, R/2 выполняется условие (11.1). Очевидно, последовательность элементов с индексами i = R/2+1, R/2+2, …, R (листьев двоичного дерева), является пирамидой, поскольку для этих индексов в пирамиде нет сыновей.

Способ построения пирамиды «на том же месте» был предложен Р. Флойдом. В нем используется процедура просеивания (sift), которуюрассмотрим на следующем примере.

Предположим, что дана пирамида с элементами K[3], K[4], …, K[10] нужно добавить новый элемент K[2] для того, чтобы сформировать расширенную пирамиду K[2], K[3], K[4], …, K[10]. Возьмем, например, исходную пирамиду K[3], …, K[10], показанную на рисунке 11.5, и расширим эту пирамиду «влево», добавив элемент K[2]=44.

Рисунок 11.5 - Пирамида, в которую добавляется ключ K[2]=44

Добавляемый ключ K[2] просеивается в пирамиду: его значение сравнивается с ключами узлов-сыновей, т. е. со значениями 15 и 28. Если бы оба ключа-сына были больше, чем просеиваемый ключ, то последний остался бы на месте, и просеивание было бы завершено. В нашем случае оба ключа‑сына меньше, чем 44, следовательно, вставляемый ключ меняется местами с наименьшим ключом в этой паре, т. е. с ключом 15. Ключ 44 записывается в элемент K[4], а ключ 15 - в элемент K[2]. Просеивание продолжается, поскольку ключи-сыновья нового элемента K[4] оказываются меньше его - происходит обмен ключей 44 и 18. В результате получаем новую пирамиду, показанную на рисунке 11.6.

В нашем примере получалось так, что оба ключа-сына просеиваемого элемента оказывались меньше его. Это не обязательно: для инициализации обмена достаточно того, чтобы оказался меньше хотя бы один дочерний ключ, с которым и производится обмен.

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

Рисунок 11.6 - Просеивание ключа 44 в пирамиду

Алгоритм просеивания в пирамиду допускает рекурсивную формулировку:

1) просеивание элемента с индексом temp,

2) при выполнении условий остановки - выход,

3) определение индекса q элемента, с которым выполняется обмен,

4) обмен элементов с индексами temp и q,

5) temp:= q,

6) перейти к п. 1.

Этот алгоритм в применении к нашему массиву а реализован в подпрограмме Sift, которая выполняет просеивания в пирамиду с максимальным индексом R:

Procedure Sift(temp, R: Integer);

Var q: integer;

x: TElement;

q:=2*temp;

If q > R Then Exit;

If q < R Then

If a[q-1].Key > a[q].Key Then q:= q + 1;

If a[temp-1].Key <= a[q-1].Key Then Exit;

x:= a[temp-1];

a[temp-1]:= a[q-1];

a[q-1]:= x;

temp:= q;

Shift(temp, R);

End;

Процедура Shift учитывает индексацию вектора а от нуля.

Теперь рассмотрим процесс создания пирамиды из массива a[0], a[1], …, a[HighIndex]. Напомним, что элементы этого массива индексируются от 0, а пирамида от 1 и, кроме того, N = HighIndex+1. Ясно, что элементы a[N/2], a[N/2+1], …, a[HighIndex] уже образуют пирамиду, поскольку не существует двух индексов i (i= N/2+1, N/2+2,…) и j, таких, что, j=2i (или j=2i+1). Эти элементы составляют последовательность, которую можно рассматривать как листья соответствующего двоичного дерева. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место. Этот процесс иллюстрируется следующим примером.

Процесс построения пирамиды (жирным шрифтом отмечены ключи, образующие пирамиду на текущем шаге ее построения):

Следовательно, процесс построения пирамиды из N элементов «на том же месте» можно описать следующим образом:

R:= N;

For i:= N Div 2 Downto 1 Do

Sift(i, R);

Для того, чтобы получить не только частичную, но и полную упорядоченность элементов нужно проделать Nсдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший элемент). Возникает вопрос, где хранить «всплывающие» верхние элементы? Существует такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х), прятать верхний элемент на место х, а х посылать в начало пирамиды в качестве элемента a[0] и просеивать его в нужное место. В следующей таблице приводятся необходимые в этом случае шаги:

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

Этот процесс описывается с помощью процедуры Sift следующим образом:

For R:= HighIndex Downto 1 Do Begin

x:=a[0]; a[0]:= a[R]; a[R]:= x;

Sift(1, R);

End;

Из примера сортировки видно, что на самом деле в результате мы получаем последовательность в обратном порядке. Но это легко можно исправить, изменив направление отношения порядка в процедуре Sift (в третьем и четвертом операторах If текста процедуры Sift, приведенного выше). В результате получаем следующую процедуру PyramidSort, учитывающую специфику индексации вектора a:

Procedure PyramidSort;

Var R, i,: integer;
x: TElement;

R:= N;

For i:= N Div 2 Downto 1 Do

Sift(i, R);

For R:= HighIndex Downto 1 Do Begin

x:=a[0]; a[0]:= a[R]; a[R]:= x;

Sift(1, R);

End;

С первого взгляда неочевидно, что этот метод сортировки дает хорошие результаты. Ведь элементы с большими ключами вначале просеиваются влево, прежде чем, наконец, окажутся справа. Действительно, эта процедура не рекомендуется для небольшого числа элементов, как, скажем, в нашем примере. Однако для больших значений N пирамидальная сортировка оказывается очень эффективной, и чем больше N, тем эффективнее.

Пирамидальная сортировка требует N×log₂N шагов даже в худшем случае. Такие отличные характеристики для худшего случая - одно из самых выгодных качеств пирамидальной сортировки.

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

11.2.8 Быстрая сортировка разделением

Этот метод основан на принципе обмена. К. Хоар, создатель метода, окрестил его быстрой сортировкой (QuickSort).

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Реализуется она на основе следующего алгоритма: выбирается любой произвольный элемент массива, называемый медианой далее массив просматривается слева направо до тех пор, пока не будет найден элемент c ключом, большим ключа медианы, допустим это элемент a[i]. Затем массив просматривается справа налево, пока не будет найден элемент a[j], ключ которого меньше ключа медианы. Найденные элементы a[i] и a[j] меняются местами. Затем продолжается процесс «просмотра с обменом», пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими медианы; и правую - с большими ключами.

Обычно в качестве медианы выбирается срединный элемент. Если, например, выбрать средний ключ, равный 42, из массива ключей

44, 55, 12, 42, 94, 06, 18, 67,

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

Конечные значения индексов i=5 и j=3. Ключи a[0],..., a[i-2] меньше или равны ключу x=42, ключи a[j],..., a[HighIndex] больше или равны x. Следовательно, мы получили два подмассива

a[k].Кey £ x.Кey для k=0,..., i-2,

a[k].Кey ³ x.Кey для k=j,..., HighIndex.

Наша цель - не только разделить исходный массив элементов на большие и меньшие ключи, но также рассортировать его. Однако от разделения до сортировки один шаг: разделив массив нужно сделать то же самое с обеими частями, затем с частями этих частей и т. д., пока каждая часть не будет содержать только один элемент. Этот метод представлен следующей подпрограммой Partition, учитывающей особенности индексации сортируемого массива а:

Procedure Partition(L, R: Integer);

Var i, j: integer;

w, x: TElement;

If L=R Then Exit;

i:= L; j:= R;

x:= a[(L+R) div 2 - 1];

While a[i-1].Key < x.Key Do i:= i+1;

While a[j-1].Key > x.Key Do j:= j-1;

If i <= j Then Begin

w:= a[i-1]; a[i-1]:= a[j-1]; a[j-1]:= w;

i:= i+1; j:= j-1;

End;

Until i > j;

If L < j Then Partition(L, j);

If i < R Then Partition(i, R);

End;

Для запуска процесса сортировки нужно выполнить процедуру QuickSort, которая имеет простую структуру:

Procedure QuickSort;

Partition(1, N);

End;

Обменная сортировка разделением - самый эффективный из известных методов внутренней сортировки. Это связано с небольшим числом обменов, выполняемых на большие расстояния. Однако быстрая сортировка все же имеет свои «подводные камни». Прежде всего, при небольших значениях N ее эффективность невелика, как и у всех усовершенствованных методов.

В случае если сортируемые данные не помещаются в оперативной памяти, а расположены на внешнем запоминающем устройстве, то методы их обработки называют «внешними методами», например, «внешний поиск», «внешняя сортировка». Исторически получилось так, что до повсеместного использования файлов прямого доступа сортируемые таблицы большого размера размещали на магнитных лентах, которые допускали только последовательный доступ. При последовательном доступе для перехода от любого текущего элемента, например х, к элементу y, расположенному перед х, приходится просматривать всю исходную таблицу с начала. Пример оперативной структуры с последовательным доступом – линейный односвязный список. В общем случае структура с последовательным доступом характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному элементу. Это - строгое ограничение по сравнению с возможностями, которые дает массив (массив – оперативная структура с прямым доступом), и поэтому здесь приходится применять другие методы сортировки.

Основной метод - это сортировка слиянием. Слияние означает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние - намного более простая операция, чем сортировка; она используется в качестве вспомогательной в более сложном процессе последовательной сортировки.

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

11.3.1 Сортировка прямым слиянием

Один из методов сортировки слиянием называется прямым (простым) слиянием и состоит в следующем:

1) исходная последовательность а разбивается на две половины b и с;

2) последовательности b и c сливаются при помощи объединения отдельных элементов в упорядоченные пары;

3) полученной после слияния последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки;

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

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

a: 44, 55, 12, 42, 94, 18, 06, 67

На первом шаге разбиение дает последовательности

b: 44, 55, 12, 42

c: 94, 18, 06, 67

Разбиение предполагает, что длина всей последовательности известна и равна N. Тогда начальные N/2 элементов на ленте a последовательно переписываются на ленту b, а элементы второй половины - на ленту c. После этого лента a очищается.

Затем выполняется фаза слияния. Поскольку в текущий момент доступен только один элемент на ленте, то слияние выполняется так: извлекаются начальные элементы с лент b и c (в примере это элементы 44 и 94). Эти элементы сравниваются друг с другом, и меньший элемент (44 из b) записывается на ленту a. Затем выполняется переход к следующему элементу (к 55 на b) на той ленте, откуда он был извлечен элемент, посланный на ленту a. Теперь второй извлеченный элемент может быть записан на ленту a вторым по порядку с гарантией того, что он больше ранее записанного. Поскольку извлечение сопровождается переходом на одну позицию, то на следующем шаге начальными становятся те элементы, которые раньше были вторыми на лентах b и c. Эти элементы (55 и 18) сливаются на a, образуя упорядоченную пару.

Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пары дает

a: 44, 94, | 18, 55, | 06, 12, | 42, 67.

После завершения фазы слияния ленты b и c очищаются.

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

a: 06, 12, 44, 94, | 18, 42, 55, 67.

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

Третье разбиение и слияние приводят, наконец, к нужному результату:

a: 06, 12, 18, 42, 44, 55, 67, 94

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

Собственно говоря, фазы разбиения не относятся к сортировке, поскольку они никак не переставляют элементы; в каком-то смысле они непродуктивны, хотя и составляют половину всех операций переписи. Их можно удалить, объединив фазы разбиения и слияния. Вместо того чтобы сливать элементы в одну последовательность, результат слияния сразу распределяют на две ленты, которые на следующем проходе будут входными. В отличие от двухфазного слияния этот метод называют однофазным или сбалансированным слиянием. Он имеет явные преимущества, так как требует вдвое меньше операций переписи, но это достигается ценой использования четвертой ленты.

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

Вместо двух файлов можно легко использовать один массив, если рассматривать его как последовательность с двумя концами. Вместо того чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух концов массива. Направление пересылки сливаемых элементов меняется (переключается) после каждой упорядоченной пары на первом проходе, после каждой упорядоченной четверки на втором проходе и т. д.; таким образом равномерно заполняются две выходные последовательности, представленные двумя концами одного массива (выходного). После каждого прохода два массива меняются ролями: входной становится выходным и наоборот.

Программу можно еще больше упростить, объединив два концептуально различных массива в один двойной длины. Итак, данные будут представлены следующим образом:

a: Аrray [1..2*N] Оf TElement;

Пусть индексы i и j указывают два исходных элемента, тогда как k и l обозначают два места пересылки. Исходные данные - это элементы а[1],..., а[N]. Очевидно, что нужна булевская переменная up для указания направления пересылки данных. Условие up=true будет означать, что на текущем проходе компоненты a[1], …,a[N]будут пересылаться «направо» - в переменные a[N+1], …,a[2N]; если up=false, то a[N+1], …,a[2N] должны переписываться «налево» - в a[1], …, a[N]. Значение up строго чередуется между двумя последовательными проходами. И наконец, вводится переменная р для обозначения длины сливаемых последовательностей (р-наборов). Ее начальное значение равно 1, и оно удваивается перед каждым очередным проходом. Для простоты мы будем считать, что N (число элементов в таблице) - всегда степень двойки. Итак, программа простого слияния выглядит следующим образом:

Procedure Mergesort;

Var i, j, Jc, l, t: Word; uр: Вооlеап; p, h, m, q, r: Word;

{а имеет индексы 1..2*N}