Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Информатика » Алгоритмизация и программирование

Сортировка методом слияний

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание
Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.
Этот метод состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии  "сливаются” в одну.
Пусть массив а [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.
Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 1575 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Высокоуровневые методы информатики и программирования [28]
Информатика и программирование [34]
Информационные системы в экономике [36]
Языки программирования и методы трансляции [15]
Алгоритмизация и программирование [61]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2024 © Ni-Cd. All Rights Reserved