TURBO PASCAL

Новости

Программы   

Turbo Pascal 

Игры

Документация   

Странности

FAQ

Ссылки

Форум

Гостевая книга

Рассылка

Благодарности

Об авторе

Слияние

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

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

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

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

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

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

Мы рассмотрим 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-го результата, например:

слияние

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

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-й.

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

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

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}

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

 

 Оглавление

На первую страницу

Rambler's Top100 Rambler's Top100
PROext: Top 1000

(с)Все права защищены

По всем интересующим вопросам прошу писать на электронный адрес

Hosted by uCoz