НОВОСТИ
Новости сайта
О САЙТЕ
Содержание сайта
БИБЛИОТЕКА
Структуры и алгоритмы
ОБРАТНАЯ СВЯЗЬ
Связь с автором
Структуры и алгоритмы

Слияние

На сегодняшнем занятии мы начнем рассмотрении темы внешняя сортировка.

Внешняя сортировка сортирует файлы, которые не помещаются целиком в оперативную память.

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

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

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

Слияние - намного более простая операция, чем сортировка.

Мы рассмотрим 2 алгоритма слияния:

  1. Прямое слияние. Алгоритм Боуза - Нельсона
  2. Естественное (Неймановское) слияние.

Прямое слияние. Алгоритм Боуза - Нельсона

  1. Последовательность а разбивается на две половины b и с.
  2. Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары.
  3. Полученной последовательности присваивается имя а, после чего повторяются шаги 1 и 2; при этом упорядоченные пары сливаются в упорядоченные четверки.
  4. Предыдущие шаги повторяются, при этом четверки сливаются в восьмерки и т.д., пока не будет упорядочена вся последовательность, т.к. длины последовательностей каждый раз удваиваются.

Пример

Исходная последовательность

А = 44 55 12 42 94 18 06 67

1     b = 44 55 12 42
с = 94 18 06 67
а = 44 94' 18 55' 06 12' 42 67

2     b = 44 94' 18 55'
с =06 12' 42 67
а = 06 12 44 94' 18 42 55 67'

3     b = 06 12 44 94'
с = 18 42 55 67'
а = 06 12 18 42 44 55 67 94

Операция, которая однократно обрабатывает всё множество данных, называется фазой.

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

В нашем примере сортировка производится за три прохода. Каждый проход состоит из фазы разбиения и фазы слияния.

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

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

sli__002.gif (4975 bytes)

Если части не равны или не делятся точно пополам, процедуру уточняют надлежащим образом. Аналогично слияние "половинок" можно свести к слиянию "четвертушек", "восьмушек" и т. д.; имеет место рекурсия.

Const n=200;

Type
tipkl=word;
tip = Record
kl: tipkl;
z:Array[1..50] of real
End;

Var
A: Array[1..n] of tip;
j:word;

Procedure Bose (Var AA; voz:Boolean);
Var
m,j:word; x:tip; {tip - тип сортируемых записей}
A: Array [1..65520 div Sizeof(tip)] of tip Absolute AA;
Procedure Sli(j,r,m: word); { r - расстояние между началами
сливаемых частей, а m - их размер, j - наименьший номер записи}
Begin
if j+r<=n Then
If m=1 Then
Begin
If voz Xor (A[j].kl < A[j+r].kl) Then
Begin
x:=A[j];
A[j]:= A[j+r];
A[j+r]:=x
End
End
Else
Begin
m:=m div 2;
Sli(j,r,m); {Слияние "начал"}
If j+r+m<=n Then
Sli(j+m,r,m); {Слияние "концов"}
Sli(j+m,r-m,m) End {Слияние в центральной части}
End{блока Sli};
Begin
m:=1;
Repeat
j:=1; {Цикл слияния списков равного размера: }
While j+m<=n do
Begin
Sli(j,m,m);
j:=j+m+m
End;
m:=m+m {Удвоение размера списка перед началом нового прохода}
Until m >= n {Конец цикла, реализующего все дерево слияний}
End{блока Bose};
BEGIN
Randomize;
For j:=1 to n do
begin
A[j].kl:= Random(65535);
Write(A[j].kl:8);
end;
Readln;
Bose(A,true);
For j:=1 to n do
Write(A[j].kl:8);
Readln
END.

Естественное (Неймановское) слияние.

Она объединяются упорядоченные части, спонтанно возникшие в исходном массиве; они могут быть также следствием предыдущей обработки данных. Рассчитывать на одинаковый размер сливаемых частей не приходится.
Записи, идущие в порядке неубывания ключей, сцепляются, образуя подсписок. Минимальный подсписок одна запись.

Пример:

Пусть даны ключи записей
5    7    8    3    9     4    1    7    6

Ищем подсписки

sli__004.gif (1427 bytes)

В один общий список соединяются 1-й, 3-й, 5-й и т. д. подсписки, в другой - 2-й, 4-й и т. д. подсписки.

Произведем слияние 1 подсписка 1 списка и 1 подсписка 2 списка, 2 подсписка 1 списка и 2 подсписка 2 списка и т.д.

Будут получены следующие цепи

3 --> 5 --> 7 --> 8 --> 9 и 1 --> 4 --> 7

Подсписок, состоящий из записи "6", пары не имеет и "принудительно" объединяется с последней цепью, принимающей вид 1 --> 4--> 6 --> 7.

При нашем небольшом числе записей 2-й этап, на котором сливаются две цепи, окажется последним.

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

Для программной реализации заводят массив sp: элемент sp[i] - это номер записи, которая следует за i-й.

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

sli__006.gif (6831 bytes)

Repeat {Повторение актов слияний подсписков}
If A[j].kl < A[i].kl Then {Выбирается меньшая запись}
Begin sp[k]:=j; k:=j; j:=sp[j];
If j<=0 Then {Сцепление с остатком "i"-подсписка}
Begin sp[k]:=i; Repeat m:=i; i:=sp[i] Until i<=0 End
End
Else
Begin sp[k]:=i; k:=i; i:=sp[i];
If i<=0 Then {Сцепление с остатком "j"-подсписка}
Begin sp[k]:=j; Repeat m:=j; j:=sp[j] Until j<=0 End
End;
If j<=0 Then Begin sp[m]:= 0; sp[p]:=-sp[p]; i:=-i;
j:=-j; If j<>0 Then p:=r; k:=r; r:=m End
Until j=0;

{В конец сформированного подсписка всегда заносится нулевая ссылка (sp[m]:= 0), ибо он может оказаться последним.

Действие sp[p]:= -sp[p] обозначает минусом конец ранее построенного подсписка.

В переменных i,j ссылки на начала новых сливаемых подсписков - со знаком минус; его снимаем. Переход к новым подспискам требует обновления переменных p, k, r}

Итак, на сегодняшнем занятии мы рассмотрели алгоритмы слияния.

Почта /// Структуры и алгоритмы