Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.
Этот
метод состоит в разбиении данного массива на несколько частей, которые
сортируются по отдельности и впоследствии "сливаются” в одну.
Пусть
массив а [1...n ] разбивается на части длиной k, тогда первая часть
- а [ 1 ], а [ 2 ], ...., а [ k ], вторая - а [ k +1 ], а [ k + 2
], ...., а [ 2k ] и так далее. Если n не делится на k, то в последней
части будет менее k элементов.
После того как массивы - части
упорядочены, можно объединить их в упорядоченные массивы - части,
состоящие не более чем из 2 k элементов, которые далее объединить в
упорядоченные массивы длиной не более 4 k, и так далее, пока не
получится один упорядоченный массив.
Таким образом, чтобы получить
отсортированный массив этим методом, нужно многократно "сливать” два
упорядоченных отрезка массива в один упорядоченный отрезок. При этом
другие части массива не затрагиваются.
Сейчас можем описать процедуру
слияния двух упорядоченных массивов размерностей m-k и n-m
соответственно в третий упорядоченный массив, размерности n-k.
Procedure sorting4(k,m,n:integer);
var i,j:integer;
begin
i:=k+1;
j:=m+1;
k:=1;
while (i<=m) and (j<=n) do
{пока не закончилась хотя бы одна часть}
begin
if a[i]<=b[j] then
begin c[k]:=a[i]; inc(i); end
else begin c[k]:=b[j]; inc(j); end;
inc(k);
end;
{один из массивов - частей обработан полностью}
{осталось перенести в с остаток другого массива - части}
while i<=m do
begin c[k]:=a[i]; inc(i); inc(k); end;
while j<=n do
begin c[k]:=b[j]; inc(j); inc(k); end;
end;
Приведем
пример программы, использующий эту процедуру в некоторой переработке (
вместо a[k+1], ..., a[m] используем a[1..k], а вместо a[m+1], ...,
a[n] используем b[1..m], где k+m = n ). Эта программа делит исходный
массив на две части, затем каждая часть сортируется методом
"пузырьковой” сортировки, после чего части соединяются с помощью данной
процедуры в искомый массив. Очевидно, скорость такого метода выше, чем
просто использование "пузырьковой ” сортировки.
program n4;
const n=5;
type ar=array[1..n] of integer;
var k,m,i:integer;
a,b,c:ar;
Procedure sorting4;
var s,i,j:integer;
begin
i:=1;
j:=1;
s:=1;
while (i<=k) and (j<=m) do
{пока не закончилась хотя бы одна часть}
begin
if a[i]<=b[i] then
begin c[s]:=a[i]; inc(i); end
else begin c[s]:=b[j]; inc(j); end;
inc(s);
end;
{один из массивов - частей обработан полностью}
{осталость перенести в с остаток другого массива - части}
while i<=k do
begin c[s]:=a[i]; inc(i); inc(s); end;
while j<=m do
begin c[s]:=b[j]; inc(j); inc(s); end;
end;
procedure sorting2(var p:ar;len:integer);
var f,i,t:integer;
{f - номер просмотра (изменяется от 1 до n-1)
i - номер рассматриваемой пары
t - промежуточная переменная для перестановки местами элементов}
begin
for f:=1 to len-1 do
{цикл по номеру просмотра}
for i:=1 to len-f do
if p[i]>p[i+1] then
{перестановка элементов}
begin
t:=p[i];
p[i]:=p[i+1];
p[i+1]:=t;
end;
end;
begin
k:=n div 2;
m:=n-k;
writeln('Введите исходный массив:');
for i:=1 to n do read(c[i]);
for i:=1 to k do a[i]:=c[i];
for i:=1 to m do b[i]:=c[k+i];
sorting2(a,k);
sorting2(b,m);
sorting4;
writeln('Отсортированный массив:');
for i:=1 to n do write(c[i],' ');
writeln;
end.
