Естественное двухпутевое слияние, нужен исходник!!! Опции

[Юлия]

Люди!!! Очень нужен исходник!!!
Почему-то по просто двухпутевому слиянию - материала море, а про "естественное" - ни слова.
ХЕЛП!!!

[volvo]

По аналогии и не получится... Не пишутся программы по аналогии... Вот так я бы реализовал метод естественных слияний:

Исходный код

const
arr_size = 50;
type
ttype = integer;
tvector = array[0 .. pred(arr_size)] of ttype;

var
B: tvector;

procedure merge(var A : array of ttype; p, q, r : longint);
var
k, i, j : longint;
begin
for k := 0 to r - p do
B[k] := A[k+p];

i := 0;
j := q-p+1;
for k := 0 to r - p do begin

if (i > q-p) or (j > r-p) then begin
if i > q-p then begin
A[p+k] := B[j];
inc(j);
end
else begin
A[p+k] := B[i];
inc(i);
end;

continue;
end;

if B[i] > B[j] then begin
A[p+k] := B[j];
Inc(j);
end
else begin
A[p+k] := B[i];
Inc(i);
end;

end;
end;


procedure merge_sort(var arr: array of ttype; p, r: longint);
var
q: longint;
begin

if p < r then begin
q := (p + r) div 2;

MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
end;

end;

procedure create_vector(var vec: array of ttype;
n: integer);
var i: integer;
begin
for i := 0 to pred(n) do
vec[i] := random(100);
end;
procedure print_vector(var vec: array of ttype;
n: integer);
var i: integer;
begin
for i := 0 to pred(n) do
write(vec[i]:5);
end;

var
arr: tvector;

begin
writeln; writeln('before:');
create_vector(arr, arr_size);
print_vector(arr, arr_size);

writeln; writeln('after:');
merge_sort(arr, 0, pred(arr_size));
print_vector(arr, arr_size);
end.

Попробуй преобразовать это в процедуру, и сделать то, что тебе нужно...

P.S. Я бы немного изменил твою программу. Ты производишь однотипные действия неоднократно. Имеет смысл в таком случае вынести их в функцию. Смотри:

Function GetSeconds: Real;
Var hour, min, sec, hund: word;
Begin
  GetTime(hour,min,sec,hund);
  GetSeconds := sec+hund*0.01+min*60+hour*3600;
End;
...
{ и теперь при вызове InsertionSort делать так: }
vector(n, ARRAYSIZE, a); {формирование произвольного вектора длинны n}
T := GetSeconds;
InsertionSort(n, a); { сортировка произвольного вектора }
T := GetSeconds - T; { T = время выполнения сортировки в секундах }

А из самой InsertSort все, что связано с вычислением времени - убрать...

Во-первых, программа станет проще для понимания. Во-вторых - процедура сортировки не перегружается лишними вычислениями, а делает ТОЛЬКО то, что должна делать. В третьих, эту же функцию GetSeconds можно применять и при определении быстродействия других методов сортировки... Подумай над этим ;)

[Jill]

Подумай над этим ;)

кст, думала ;)
там действительно много повторов


так все несложно получается...не то, что с теми внешними файлами...здорово!
ПАСИБА!!! :zdorov: