Работа 3.6 Упр.28 ГДЗ Семакин 10 класс (Информатика)

Задача

1) каждая пара соседних элементов сливается в одну группу из двух элементов (последняя группа может состоять из одного элемента);
2) каждая пара соседних двухэлементных групп сливается в одну четырехэлементную группу и т. д.
При каждом слиянии новая укрупненная группа упорядочивается.

Подробный ответ

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

Ниже приведён корректный вариант программы на Pascal.

type mas=array[0..100] of integer;
procedure MergeSort(var m:mas;n:integer);
var
  i,l1,l2,j,k,tmp,len:integer;
  c:boolean;
begin
  len:=1;
  c:=true;
  while len<n do
  begin
    if c then
    begin
      i:=0;
      while i+len<=n do
      begin
        l1:=i+1;
        l2:=i+len+1;
        j:=i+2*len;
        if j>n then j:=n;
        while (l1<=i+len) or (l2<=j) do
        begin
          if l1>i+len then
          begin
            while l2<=j do
            begin
              i:=i+1;
              m[i]:=m[l2];
              l2:=l2+1;
            end;
          end
          else if l2>j then
          begin
            while l1<=i+len do
            begin
              i:=i+1;
              m[i]:=m[l1];
              l1:=l1+1;
            end;
          end
          else if m[l1]>m[l2] then
          begin
            i:=i+1;
            m[i]:=m[l2];
            l2:=l2+1;
          end
          else
          begin
            i:=i+1;
            m[i]:=m[l1];
            l1:=l1+1;
          end;
        end;
        i:=j;
      end;
      while i<n do
      begin
        i:=i+1;
        m[i]:=m[i-1];
      end;
    end
    else
    begin
      i:=0;
      while i+len<=n do
      begin
        l1:=i+1;
        l2:=i+len+1;
        j:=i+2*len;
        if j>n then j:=n;
        while (l1<=i+len) or (l2<=j) do
        begin
          if l1>i+len then
          begin
            while l2<=j do
            begin
              i:=i+1;
              m[i]:=m[l2];
              l2:=l2+1;
            end;
          end
          else if l2>j then
          begin
            while l1<=i+len do
            begin
              i:=i+1;
              m[i]:=m[l1];
              l1:=l1+1;
            end;
          end
          else if m[l1]>m[l2] then
          begin
            i:=i+1;
            m[i]:=m[l2];
            l2:=l2+1;
          end
          else
          begin
            i:=i+1;
            m[i]:=m[l1];
            l1:=l1+1;
          end;
        end;
        i:=j;
      end;
      while i<n do
      begin
        i:=i+1;
        m[i]:=m[i-1];
      end;
    end;
    len:=2*len;
    c:=not c;
  end;
  if not c then
  begin
    i:=1;
    repeat
      m[i-1]:=m[i-1];
      i:=i+1;
    until not(i<=n);
  end;
end;
var a:mas;
n,i:integer;
begin
  clrscr;
  randomize;
  write(‘n=’);readln(n);
  writeln(‘Исходный массив:’);
  for i:=0 to n-1 do
  begin
    a[i]:=random(20);
    write(a[i],’ ‘);
  end;
  writeln;
  MergeSort(a,n);
  writeln(‘Сортировка:’);
  for i:=0 to n-1 do
  write(a[i],’ ‘);
end.

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

Ответ: программа сортировки массива методом слияния.

Оцени решение

← Предыдущий Следующий →

Сообщить об ошибке

Общая оценка

3.7 / 5

Другие учебники