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

[Юлия]

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

[Jill]

подниму тему с вашего разрешения

СУТЬ: задание состоит из двух подзаданий:
Разработать программы, реализующие сортировки:
1. Методом Шелла
2. Естественным двухпутевым слиянием
Исследовать работу программы на сортировке n чисел, если они:
a) расположены случайным образом;
B) отсортированы;
c) отсортированы в обратном порядке;
С первым подзаданием справилась:

uses Crt,Dos;
const ARRAYSIZE=5000;
type arrayType=array[1..ARRAYSIZE] of integer;
var
  A:arrayType;{Сортируемый вектор}
  n:integer;{Количество точек в сортируемом векторе}
  exp:integer;{Количество проводимых экспирементов}
  point:byte;{Количество точек требуемое для построения графика}
  step:integer;{Шаг для построения графика}
  i,j,k:integer;{Переменные цикла}
  c:integer;{Вспомогательная переменная для обмена двух элементов}
  f:text;{Файловая переменная для записи результатов}
  t:real;{Время сортировки вектора}
  aver_time:array[1..3]of real;{среднее время сортировки при разном расположении}
                     {элементов (1-случайный порядок, 2-обратный,3-прямой)}

procedure InsertionSort(Size:integer;var theArray:arrayType; var time:real);
var
  newPos:integer;{Начальная позиция вставляемого на место элемента}
  newValue:integer;{Значение вставляемого на место элемента}
  currentPos:integer;{Позиция вставляемого эл. в упорядоченном векторе}
  hour,min,sec,hund:word;{текущее время (час, мин, сек, сотые}
  start_time,finish_time:real;{время начала и окончания сортировки вектора}
  h,t,s:word;
begin
{Вычисление шага сортировки}
t:=1;
h:=1;
While h<Size do
  begin
  t:=t+1;
  h:=3*h+1;
  end;
if t>2 then begin
             t:=t-2;
             h:=round(h/3);
             end;

  GetTime(hour,min,sec,hund); {фиксируем время начала сортировки}
  start_time:=sec+hund*0.01+min*60+hour*3600; {переводим время в секунды}
{Алгоритм сортировки}
for s:=t downto 1 do
begin
 h:=round(h/3);
for newPos:=h+1 to SIZE do
begin
   newValue:=theArray[newPos];
   currentPos:=newPos-h;
   while (currentPos>=1)and(theArray[currentPos]>newValue)do
   begin
     theArray[currentPos+h]:=theArray[currentPos];
     currentPos:=currentPos-h;
   end;
   theArray[currentPos+h]:=newValue;
 end;
end;
GetTime(hour,min,sec,hund);{фиксируем время окончания сортировки}
finish_time:=sec+hund*0.01+min*60+hour*3600;{переводим время в секунды}
time:=finish_time-start_time;{определяем фактическое время сортировки}
end;{InsertionSort}

procedure Vector(SIZE,MAX:integer;var theArray:arrayType);
var i:integer;{Номер текущего элемента вектора}
begin
  randomize;
  for i:=1 to SIZE do
   theArray[i]:=random(MAX);
end;{Vector}

{Основной модуль}
begin
   ClrScr;
   assign(f,'c:\primer\ins');{инициализация выходного файла}
   rewrite(f);
   write('Введите необходимое количество точек для построения графика ->');
   readln(point);
   step:=round(ARRAYSIZE/point);
   write('Введите количество экспериментов ->');
   readln(exp);
 {Формирование заголовка таблицы}
   writeln(f,'Среднее время сортировки элементов:');
   writeln(f,' кол-во  ',' случайные',' обратное',' сортиров.');
   writeln(f,'элементов');
   for k:=1 to point do
   begin
     n:=step*k;{определение длины вектора для k шага}
     for i:=1 to 3 do
       aver_time[i]:=0.0; {обнуление времени}
     for j:=1 to exp do
     begin
       vector(n,ARRAYSIZE,a);{формирование произвольного вектора длинны n}
       InsertionSort(n,a,t);{сортировка произвольного вектора}
      {накопление времени для определения среднего}
       aver_time[1]:=aver_time[1]+t;
      {формирование вектора в обратном порядке}
       for i:=1 to n div 2 do
        begin
          c:=a[i];
          a[i]:=a[n-i+1];
          a[n-i+1]:=c;
        end;
       InsertionSort(n,a,t);{сортировка обратно сортированного вектора}
       aver_time[2]:=aver_time[2]+t;
       InsertionSort(n,a,t);{сортировка упорядоченного вектора}
       aver_time[3]:=aver_time[3]+t;
     end;
   {нахождение среднего времени сортировки, исходя из m экспериментов}
     for i:=1 to 3 do
      aver_time[i]:=aver_time[i]/exp;
   {заполнения таблицы результатов в файле}
     write(f,n:7,'  ');
     for i:=1 to 3 do
      write(f,aver_time[i]:7:2,'   ');
      writeln(f);
  end;
close(f);
end.

а вот со вторым - ни в какую!!! смысл тот же, а вот с примером, ссылка на который приведена выше, разобраться не могу
не понимаю, зачем там необходимы целых ТРИ внешних файла? и как переписать его так, чтобы этих внешних файлов не было вообще - просто случайный вектор, просто сортировка / внешний файл - только один - с результатами подсчета времени.
помогите, пожалуйста!!!

[volvo]

не понимаю, зачем там необходимы целых ТРИ внешних файла?

Понимаешь, в чем дело ... Алгоритм сортировки естественным слиянием относится к внешней сортировке (сортировке файлов) по определению. Поэтому и используется 3 файла - 2 исходных, и результат.

Кстати, что значит

а вот со вторым - ни в какую!!!

? Что именно ты считаешь вторым подзаданием? Сортировку уже отсортированных чисел? Или метод слияний вообще?

как переписать его так, чтобы этих внешних файлов не было вообще - просто случайный вектор

Если на то пошло, то НЕ ОДИН, а 2 вектора, т.к. тебе надо делать слияние...

[Jill]

Поэтому и используется 3 файла - 2 исходных, и результат.

в том примере исходный - ОДИН файл! точно а два остальных...промежуточные наверное

Что именно ты считаешь вторым подзаданием? Сортировку уже отсортированных чисел? Или метод слияний вообще?

второе подзадание - это метод слияний / по аналогии с первой программой надо сделать вторую / не получается