VPF::[Pascal|VB 6] Margesort algorithm - Форум программистов

BioSharK

Дата 16.12.2009, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 15.9.2009

Репутация: нет
Всего: нет

Нужно ввести масив чисел и отсортировать их по возрастанию. (margesort' ом)
помогите.

Hinidu

Дата 16.12.2009, 21:01 (ссылка)

(голосов:1)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 5.12.2009
Где: Калининград

Репутация: нет
Всего: нет

Код


Procedure MergeSort(var a: TArray; l,r: integer);
//-----------------------------------------------
Procedure Merge(var a: TArray; l,q,r: integer);
var a1,a2: array [1..100000] of integer; i,j1,j2,len1,len2: integer;
begin
len1:=q-l+1;
for i:=1 to len1 do a1[i]:=a[l-1+i];
len2:=r-q;
for i:=1 to len2 do a2[i]:=a[q+i];
a1[len1+1]:=High(integer);
a2[len2+1]:=High(integer);
j1:=1; j2:=1;
for i:=l to r do
  if a1[j1]<a2[j2] then
    begin
    a[i]:=a1[j1];
    inc(j1)
    end
  else
    begin
    a[i]:=a2[j2];
    inc(j2)
    end
end;
//--------------------------------------------------
var q: integer;
begin
if l<r then
  begin
  q:=(l+r) div 2;
  MergeSort(a,l,q);
  MergeSort(a,q+1,r);
  Merge(a,l,q,r)
  end
end;

BioSharK

Дата 17.12.2009, 16:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 15.9.2009

Репутация: нет
Всего: нет

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

Hinidu

Дата 17.12.2009, 21:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 5.12.2009
Где: Калининград

Репутация: нет
Всего: нет

Код


const MaxN = 100000;
type  TArray = array [1..MaxN] of integer;
var    a: TArray;
         n,i: integer;

Procedure MergeSort(var a: TArray; l,r: integer);
//-----------------------------------------------
Procedure Merge(var a: TArray; l,q,r: integer);
var a1,a2: array [1..MaxN div 2] of integer; i,j1,j2,len1,len2: integer;
begin
len1:=q-l+1;
for i:=1 to len1 do a1[i]:=a[l-1+i];
len2:=r-q;
for i:=1 to len2 do a2[i]:=a[q+i];
a1[len1+1]:=High(integer);
a2[len2+1]:=High(integer);
j1:=1; j2:=1;
for i:=l to r do
  if a1[j1]<a2[j2] then
    begin
    a[i]:=a1[j1];
    inc(j1)
    end
  else
    begin
    a[i]:=a2[j2];
    inc(j2)
    end
end;
//--------------------------------------------------
var q: integer;
begin
if l<r then
  begin
  q:=(l+r) div 2;
  MergeSort(a,l,q);
  MergeSort(a,q+1,r);
  Merge(a,l,q,r)
  end
end;

begin
read(n);
for i:=1 to n do
  read(a[i]);
MergeSort(a,1,n);
for i:=1 to n do
  writeln(a[i]);
end.

a: исходный массив, a1: левая часть подмассива а в диапазоне от l до q, а2: правая часть подмассива а в диапазоне от q+1 до r. Советую найти второе издание книги Кормена "Алгоритмы. Построение и анализ", в ней почти в самом начале есть подробный разбор этого алгоритма.

Это сообщение отредактировал(а) Hinidu - 17.12.2009, 21:10

BioSharK

Дата 18.12.2009, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 15.9.2009

Репутация: нет
Всего: нет

Код


uses crt;
var a,b,c:array[1..500] of integer;
    n,m,i,j,k:integer;
begin
clrscr;
write('n=');readln(n);
write('m=');readln(m);
writeln('Massiv A:');
for i:=1 to n do
   begin
    a[i]:=2*i+1;{введем нечетные числа}
    write(a[i],' ');{введем четные числа}
   end;
writeln;
writeln('Massiv B:');
for i:=1 to m do
   begin
    b[i]:=2*i;
    write(b[i],' ');
   end;
writeln;
i:=1; j:=1; k:=1; {устанавливаем счётчики}
while (i<=n) or (j<=m) do {пока не дошли до конца каждого из массивов}
  begin
   if (i<=n) and (j<=m) then {если оба массива ещё не закончились}
     begin
       if a[i]<b[j] then {то пишем в новый массив меньший из текущих элементов}
        begin
         c[k]:= a[i];
         inc (i); {переходим к следующему элементу соответствующего массива}
         inc (k); {переходим к следующему элементу конечного массива}
        end
       else
        begin
         c[k]:= b[j];
         inc (j);
         inc (k);
        end
     end
   else if j>m then {иначе один из массивов уже закончился}
     begin {и мы пишем из того, в котором ещё есть элементы}
       c[k]:= a[i];
       inc (i);
       inc (k);
     end
   else if i>n then
     begin
       c[k]:= b[j];
       inc (j);
       inc (k);
     end;
  end;
writeln('Massiv C:');
for i:=1 to m+n do
write(c[i],' ');
readln
end.

вот, нашел еще коечто, но здесь значения начинает выводить с 2-ки, а не с 1. подскажите что нужно поправить

Hinidu

Дата 18.12.2009, 23:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 5.12.2009
Где: Калининград

Репутация: нет
Всего: нет

Потому что в этом цикле

Код


for i:=1 to n do
   begin
    a[i]:=2*i+1;{введем нечетные числа}
    write(a[i],' ');{введем четные числа}
   end;

при i=1 вы получаете 3, чтобы появилась единица измените 3ю строку на

Код


a[i]:=2*i-1;{введем нечетные числа}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »