Сортировки со слиянием, как правило, применяются в тех случаях, когда требуется отсортировать последовательный файл, не помещающийся целиком в основной памяти.
Алгоритм слияния (на примере массива)
Для слияния выполняются следующие действия: сравниваются p[1] и q[1], и меньшее из значений записывается в r[1]. Предположим, что это значение p[1]. Тогда p[2] сравнивается с q[1] и меньшее из значений заносится в r[2]. Предположим, что это значение q[1]. Тогда на следующем шаге сравниваются значения p[2] и q[2] и т.д., пока мы не достигнем границ одного из массивов. Тогда остаток другого массива просто дописывается в "хвост" массива r.
Алгоритм сортировки прямым слиянием
Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4), ..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей.
Реализация для типизированного файла (Turbo Pascal)
Процедура MergeSort на входе запрашивает только доступ к сортируемому файлу.
Далее на жестком диске компьютера создаются 2 вспомогательных файла B и C, в которые будут распределены записи из главного файла A. После выполнения сортировки файлы автоматически сотрутся с внешнего носителя.
Алгоритм сортировки состоит из нескольких этапов:
1) Начальное распределение записей из файла A в файлы B и C.
2) Сравнение записей из файлов В и C и постепенное слияние в файл A.
3) Вывод на экран содержимого файла A после слияния. Производится поэтапно после каждого распределения в упорядоченные пары.
Процедура метода прямого слияния выглядит следующим образом:
procedure MegreSort(var a: files);
{
/Методы внешней сортировки/
/Сортировка файла прямым слиянием/
Обозначения:
Элемент = запись. Для файлов - запись,
для переменных внутри кода - элемент
Основная процедура.
a - сортируемый типизированный файл
}
var
k, l: integer; { переменные для занесения значений из файлов B и C соответственно }
col, count, reg, grB, grC, n: integer;
i, j: integer; { счетчики для циклов }
b, c: file of integer; { вспомогательные файлы }
begin
n := filesize(a); { rколичество компонент в сортируемом файле A }
reset(a);
writeln('Этапы слияния в файл A: ');
assign(b, 'B.bmr');
assign(c, 'C.bmr');
col := 2; { количество элементов для сравнения "между собой" }
count := 1; { количество элементов в группе-связке }
{
Главный цикл:
пока количество введенных чисел не будет = количеству
чисел в группе-связке, т.е. пока не будут упорядочены все записи в файле A.
Это значит, что при распеределении записей из A в один из вспомогательных
файлов будут помещены все записи (чего, разумеется, быть не должно). Цикл
останавливается до этого действия
}
while n >= count do
begin
reg := 1; { регулирует занесении записей в файлы при распределении }
reset(a);
rewrite(b);
rewrite(c);
{
Распределение записей из файла A
в файлы B и C при разбиении.
Распределение происходит по четности.
Переменная reg после каждого занесения записей в файлы
подбирает чередующиеся позиции указателя в файле A
во избежание занесения в один и тот же файл
не предназначавшихся ему записей
}
{ Добавление в файл B }
{---------------------------------------------------------------------------}
while not eof(a) do
begin
if odd(filepos(a) + reg) then
begin
i := 1;
repeat
{
В файл должно быть занесено count элементов.
1 цикл = 1 группа-связка
}
if filepos(a) <> n then
begin
read(a, k);
write(b, k);
end;
if filepos(a) mod 2 = 0 then
reg := 2
else
reg := 1;
if (eof(a)) then
break;
inc(i);
until (i > count) or (eof(a));
end
else
{ Добавление в файл C }
begin
i := 1;
repeat
{
В файл должно быть занесено count элементов.
1 цикл = 1 группа-связка
}
if filepos(a) <> n then
begin
read(a, k);
write(c, k);
end;
if filepos(a) mod 2 = 0 then
reg := 1
else
reg := 2;
if (eof(a)) then
break;
inc(i);
until (i > count) or (eof(a));
end;
end;
{--------------------------------------------------------------------------}
{
Сравнение записей из файлов В и C
и постепенное слияние в файл A
}
rewrite(a);
reset(b);
reset(c);
{
Если количество чисел в файле A не является степенью 2, т.е. могут
оборазовываться неполные группы-связки, то для подсчтеа правильного
количества пар групп-связок добавляем единицу, отбрасыая нецелый остаток
}
if n mod col <> 0 then
reg := 1
else
reg := 0;
for i := 1 to trunc(n / col) + reg do
{ "n/col" - количество пар групп-связок, которые необходимо сравнить между собой }
begin
grB := 0; { обнуление счетчиков для }
grC := 0; { последующего сравнения }
{
Сравнения.
Здесь идет распределение по группам: все полные и неполные
считаются отдельно.
В блоке для полных пар могут оставаться от 1 до |grB - grC| записей.
Цикл идет до "количества элементов, над которыми производится
сравнение" - 1, т.к., например, для сравнения 4 чисел при
"худшем сравнении"
(т.е. когда записи из каждого файла поочередно больше друг друга)
в файл запишутся только 3, а последний элемент будет заноситься
уже как "оставшийся". В блоке неполных пар высчитываетются позиции
"оставшихся файлов" и взависимости от количества записей в обоих
файлах либо сортируются слиянием, либо (если достигнут конец
одного из файлов) просто добавляются "оставшиеся"
}
{-----Сортировка неполных групп-связок-----}
if (i = trunc(n / col) + reg) and (reg = 1) then { есть неполные группы-связки }
begin
if n mod col <= count then { проверяется условие на количество элементов в обоих файлах }
begin
seek(b, filesize(b) - n mod col); { высчитываются позиции в каждом файле }
seek(c, filesize(c));
end
else
begin
seek(b, filesize(b) - (n mod col - (n mod col - count))); { высчитываются позиции в каждом файле }
seek(c, filesize(c) - (n mod col - count));
end;
if filepos(c) = filesize(c) then { есть пустой файл }
while not eof(b) do { добавляем оставшиеся из другого }
begin
read(b, k);
write(a, k);
end
else { иначе сортируем }
begin
j := 1;
while true do
begin
if j = 1 then
{
Изначально нужно прочесть сразу обе записи,
далее по одной из каждого файла
}
begin
read(b, k);
read(c, l);
end;
{
Сравнение отдельных элементов из групп-связок между собой
и последующее слияние в файл A
}
if k < l then
begin
write(a, k);
if not eof(b) then
read(b, k)
else
begin
seek(c, filepos(c) - 1); { предотвращение лишнего прочтения в цикле }
break;
end;
end
else
begin
write(a, l);
if not eof(c) then
read(c, l)
else
begin
seek(b, filepos(b) - 1); { предотвращение лишнего прочтения в цикле }
break;
end;
end;
inc(j);
end;
if eof(c) then
while not eof(b) do
begin
read(b, k);
write(a, k);
end
else
while not eof(c) do
begin
read(c, l);
write(a, l);
end;
end;
end
else
{-----Сортировка полных групп-связок-----}
begin
for j := 1 to col - 1 do
begin
if j = 1 then
{
Изначально нужно прочесть сразу обе записи,
далее по одной из каждого файла
}
begin
read(b, k);
read(c, l);
end;
{
Сравнение отдельных элементов из групп-связок между собой
и последующее слияние в файл A
}
if k < l then
begin
write(a, k);
inc(grB); { счетчик для count }
if (grB <> count) then { предотвращение лишнего прочтения }
read(b, k)
else
break;
end
else
begin
write(a, l);
inc(grC); { счетчик для count }
if (grC <> count) then { предотвращение лишнего прочтения }
read(c, l)
else
break;
end;
end;
{------------------------------------------------------------------------------------------}
{ занесение в файл A "оставшихся" элементов (записей) }
if grB > grC then { так мы узнаем, в котором файле "остались" записи }
begin
for j := 1 to grB - grC do
begin
{
Если количество элементов в следующей паре-связке
< или = количеству записей в файле B, то записываем
элемент из файла С, иначе в B. Это сделано с целью
предотвращения оставшегося (одного) элемента в Файле B
}
write(a, l);
if not eof(c) then
read(c, l);
end;
seek(c, filepos(c) - 1); { предотвращение лишнего прочтения в цикле }
end
else
if grB < grC then { так мы узнаем, в котором файле "остались" записи }
begin
for j := 1 to grC - grB do
begin
{
Если количество элементов в следующей паре-связке
< или = количеству записей в файле B, то записываем
элемент из файла С, иначе в B. Это сделано с целью
предотвращения оставшегося (одного) элемента в Файле B
}
write(a, k);
if not eof(b) then
read(b, k);
end;
seek(b, filepos(b) - 1); { предотвращение лишнего прочтения в цикле }
end
end;
{---------------------------------------------------------------------------}
end;
reset(a);
{ вывод на экран содержимого файла A после слияния }
while not eof(a) do
begin
read(a, num);
write(num, ' ');
end;
writeln;
writeln;
col := col * 2; { повышение количества элементов для сравнения "между собой" в цикле }
count := count * 2; { повышение количества элементов в группе-связке }
end;
writeln;
close(a);
close(b);
close(c);
erase(b);
erase(c);
end;
{
/Методы внешней сортировки/
/Сортировка файла прямым слиянием/
Обозначения:
Элемент = запись. Для файлов - запись,
для переменных внутри кода - элемент
}
uses crt;
type
files = file of integer;
var
n,i, num: integer;
a: files;
procedure MegreSort(var a: files);
{
Основная процедура.
a - сортируемый типизированный файл
}
var
k, l: integer; { переменные для занесения значений из файлов B и C соответственно }
col, count, reg, grB, grC, n: integer;
i, j: integer; { счетчики для циклов }
b, c: file of integer; { вспомогательные файлы }
begin
n := filesize(a); { rколичество компонент в сортируемом файле A }
reset(a);
writeln('Этапы слияния в файл A: ');
assign(b, 'B.bmr');
assign(c, 'C.bmr');
col := 2; { количество элементов для сравнения "между собой" }
count := 1; { количество элементов в группе-связке }
{
Главный цикл:
пока количество введенных чисел не будет = количеству
чисел в группе-связке, т.е. пока не будут упорядочены все записи в файле A.
Это значит, что при распеределении записей из A в один из вспомогательных
файлов будут помещены все записи (чего, разумеется, быть не должно). Цикл
останавливается до этого действия
}
while n >= count do
begin
reg := 1; { регулирует занесении записей в файлы при распределении }
reset(a);
rewrite(b);
rewrite(c);
{
Распределение записей из файла A
в файлы B и C при разбиении.
Распределение происходит по четности.
Переменная reg после каждого занесения записей в файлы
подбирает чередующиеся позиции указателя в файле A
во избежание занесения в один и тот же файл
не предназначавшихся ему записей
}
{ Добавление в файл B }
{---------------------------------------------------------------------------}
while not eof(a) do
begin
if odd(filepos(a) + reg) then
begin
i := 1;
repeat
{
В файл должно быть занесено count элементов.
1 цикл = 1 группа-связка
}
if filepos(a) <> n then
begin
read(a, k);
write(b, k);
end;
if filepos(a) mod 2 = 0 then
reg := 2
else
reg := 1;
if (eof(a)) then
break;
inc(i);
until (i > count) or (eof(a));
end
else
{ Добавление в файл C }
begin
i := 1;
repeat
{
В файл должно быть занесено count элементов.
1 цикл = 1 группа-связка
}
if filepos(a) <> n then
begin
read(a, k);
write(c, k);
end;
if filepos(a) mod 2 = 0 then
reg := 1
else
reg := 2;
if (eof(a)) then
break;
inc(i);
until (i > count) or (eof(a));
end;
end;
{--------------------------------------------------------------------------}
{
Сравнение записей из файлов В и C
и постепенное слияние в файл A
}
rewrite(a);
reset(b);
reset(c);
{
Если количество чисел в файле A не является степенью 2, т.е. могут
оборазовываться неполные группы-связки, то для подсчтеа правильного
количества пар групп-связок добавляем единицу, отбрасыая нецелый остаток
}
if n mod col <> 0 then
reg := 1
else
reg := 0;
for i := 1 to trunc(n / col) + reg do
{ "n/col" - количество пар групп-связок, которые необходимо сравнить между собой }
begin
grB := 0; { обнуление счетчиков для }
grC := 0; { последующего сравнения }
{
Сравнения.
Здесь идет распределение по группам: все полные и неполные
считаются отдельно.
В блоке для полных пар могут оставаться от 1 до |grB - grC| записей.
Цикл идет до "количества элементов, над которыми производится
сравнение" - 1, т.к., например, для сравнения 4 чисел при
"худшем сравнении"
(т.е. когда записи из каждого файла поочередно больше друг друга)
в файл запишутся только 3, а последний элемент будет заноситься
уже как "оставшийся". В блоке неполных пар высчитываетются позиции
"оставшихся файлов" и взависимости от количества записей в обоих
файлах либо сортируются слиянием, либо (если достигнут конец
одного из файлов) просто добавляются "оставшиеся"
}
{-----Сортировка неполных групп-связок-----}
if (i = trunc(n / col) + reg) and (reg = 1) then { есть неполные группы-связки }
begin
if n mod col <= count then { проверяется условие на количество элементов в обоих файлах }
begin
seek(b, filesize(b) - n mod col); { высчитываются позиции в каждом файле }
seek(c, filesize(c));
end
else
begin
seek(b, filesize(b) - (n mod col - (n mod col - count))); { высчитываются позиции в каждом файле }
seek(c, filesize(c) - (n mod col - count));
end;
if filepos(c) = filesize(c) then { есть пустой файл }
while not eof(b) do { добавляем оставшиеся из другого }
begin
read(b, k);
write(a, k);
end
else { иначе сортируем }
begin
j := 1;
while true do
begin
if j = 1 then
{
Изначально нужно прочесть сразу обе записи,
далее по одной из каждого файла
}
begin
read(b, k);
read(c, l);
end;
{
Сравнение отдельных элементов из групп-связок между собой
и последующее слияние в файл A
}
if k < l then
begin
write(a, k);
if not eof(b) then
read(b, k)
else
begin
seek(c, filepos(c) - 1); { предотвращение лишнего прочтения в цикле }
break;
end;
end
else
begin
write(a, l);
if not eof(c) then
read(c, l)
else
begin
seek(b, filepos(b) - 1); { предотвращение лишнего прочтения в цикле }
break;
end;
end;
inc(j);
end;
if eof(c) then
while not eof(b) do
begin
read(b, k);
write(a, k);
end
else
while not eof(c) do
begin
read(c, l);
write(a, l);
end;
end;
end
else
{-----Сортировка полных групп-связок-----}
begin
for j := 1 to col - 1 do
begin
if j = 1 then
{
Изначально нужно прочесть сразу обе записи,
далее по одной из каждого файла
}
begin
read(b, k);
read(c, l);
end;
{
Сравнение отдельных элементов из групп-связок между собой
и последующее слияние в файл A
}
if k < l then
begin
write(a, k);
inc(grB); { счетчик для count }
if (grB <> count) then { предотвращение лишнего прочтения }
read(b, k)
else
break;
end
else
begin
write(a, l);
inc(grC); { счетчик для count }
if (grC <> count) then { предотвращение лишнего прочтения }
read(c, l)
else
break;
end;
end;
{------------------------------------------------------------------------------------------}
{ занесение в файл A "оставшихся" элементов (записей) }
if grB > grC then { так мы узнаем, в котором файле "остались" записи }
begin
for j := 1 to grB - grC do
begin
{
Если количество элементов в следующей паре-связке
< или = количеству записей в файле B, то записываем
элемент из файла С, иначе в B. Это сделано с целью
предотвращения оставшегося (одного) элемента в Файле B
}
write(a, l);
if not eof(c) then
read(c, l);
end;
seek(c, filepos(c) - 1); { предотвращение лишнего прочтения в цикле }
end
else
if grB < grC then { так мы узнаем, в котором файле "остались" записи }
begin
for j := 1 to grC - grB do
begin
{
Если количество элементов в следующей паре-связке
< или = количеству записей в файле B, то записываем
элемент из файла С, иначе в B. Это сделано с целью
предотвращения оставшегося (одного) элемента в Файле B
}
write(a, k);
if not eof(b) then
read(b, k);
end;
seek(b, filepos(b) - 1); { предотвращение лишнего прочтения в цикле }
end
end;
{---------------------------------------------------------------------------}
end;
reset(a);
{ вывод на экран содержимого файла A после слияния }
while not eof(a) do
begin
read(a, num);
write(num, ' ');
end;
writeln;
writeln;
col := col * 2; { повышение количества элементов для сравнения "между собой" в цикле }
count := count * 2; { повышение количества элементов в группе-связке }
end;
writeln;
close(a);
close(b);
close(c);
erase(b);
erase(c);
end;
begin
randomize;
assign(a,'input');
rewrite(a);
write('Количество записей: ');
readln(n);
writeln('Исходные данные:');
for i := 1 to n do { занесение данных в типизированный файл A }
begin
num:=random(1000)-500;
write(num,' ');
write(a, num);
end;
writeln;
writeln;
MegreSort(a);
readln;
end.