6.2. Прямое слияние
 

Сортировка, называемая прямым слиянием, выполняется следующим образом.

1. Последовательность А разбивается на две половины В и С.
2. Части В и С сливаются, при этом одиночные элементы из В и С образуют упорядоченные пары.
3. Полученная последовательность А вновь обрабатывается, как указано в двух предыдущих шагах, но сливаются упорядоченные пары. Теперь упорядоченные пары переходят в упорядоченные четверки.
4. Повторяя предыдущие шаги, сливаем четверки в восьмерки и т.д., пока не будет упорядочена вся последовательность.

Рис. Двухфазная сортировка прямым слиянием

1. Фаза разделения, когда записи из файла А разбиваются на две равные части (при нечетном числе записей в первой части на 1 больше) и помещаются в файлы В и С соответственно.
2. Фаза слияния, когда данные из файлов В и С, слитые в упорядоченные пары, четверки, восьмерки и т.д., помещаются в файл А.

Теперь рассмотрим более детально, какие операции выполняются при каждой фазе при двухфазной сортировке. Фаза разделения:

1. Открыть файл А как входной (для чтения).
2. Открыть файлы В и С как выходные (для записи).
3. Считываемые из файла А записи попеременно посылаем в файлы В и С: первая запись в файл В, вторая в С, затем третья в В, четвертая в С и т.д.
4. Закрыть файлы А, В и С.

Фаза слияния:

1. Открыть файл А как выходной (для записи).
2. Открыть файлы В и С как входные (для чтения).
3. Установить размер порции сливаемых записей. Напоминаем, что эти порции рав-ны 1,2,4,... записям для первого и последующих этапов соответственно.
4. Для каждой порции считываются по одной записи из файлов В и С.
5. Меньшая из них пересылается в файл А, и считывается очередная запись из того файла, чья запись была переслана в файл А.
6. Повторяются пункты 4 и 5 до тех пор, пока записи очередной порции одного из файлов не будут исчерпаны.
7. Оставшиеся записи из порции другого файла пересылаются в файл А.
8. Пункты 4—7 повторяются до тех пор, пока не будет достигнут конец одного из файлов В или С. Тогда оставшиеся записи из другого файла пересылаются в файл А.
9. Закрытие файлов А, В и С.

Сортировка завершается тогда, когда длина порции достигнет n. Приведем пример двухфазной сортировки прямым слиянием, записи файла — целые числа (ключи).
Пример.
/* Сортировка файла прямым слиянием, двухфазная сортировка */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main()
{int vsort1 (char* r);
int n,b; char f[40]="A";
FILE *fin,*fout;
printf("\n Создание файла А");
if ((fout=fopen(f,"w"))== NULL)
{ printf("\n Файл %s не создан",f);
getch(); return -1;
}
n=100;
printf("\n Исходный файл:\n");
while (n--)
{ b=rand();
/* заполняем файл случайными целыми числами */
fprintf(fout," %d",b);
printf("%d\t",b);
}
fclose(fout);
vsort1(f);                                               /* вызов функции внешней сортировки */
printf("\n Отсортированный файл:\n");
fin=fopen(f,"r");
while (fscanf(fin,"%d",&b) !=EOF)
printf("%d\t",b);
fclose(fin);
getch(); return 0;
}
/* ВНЕШНЯЯ ДВУХФАЗНАЯ СОРТИРОВКА ПРЯМЫМ СЛИЯНИЕМ, фаза
разделения и вызов фазы слияния */
int vsort1 (char *ff)
/* ff — исходный файл, подлежащий сортировке */
{int vsort2(char *a,int m);                                     /* функция фазы слияния */
FILE *A,*B,*C;                                                   /* файловые переменные */
int a;                                                     /* для чтения из исходного файла */
int nb,nc;                                                     /* счетчики элементов в формируемых группах */
int р;                                                     /* р=1 — признак достижения конца исходного файла */
int m=1;                                                     /* число элементов в группе: 1,2,4,8,...*/
int k=0;                                                    /"счетчик числа элементов в исходном файле */
while(1)
{if ((A=fopen(ff,"r"))== NULL)
{ printf("\n Файл %s не открывается",ff);
getch(); return -1; }
if ((B=fopen("B","w"))== NULL)
{ printf("\n Файл В1 не открывается");
getch(); return -1;
}
if ((C=fopen("C","w"))== NULL)
{ printf("\n Файл С1 не открывается");
getch(); return -1;
}
nb=0; nc=0; p=0;
while (1)
{while (1)
{ if(fscanf(A,"%d",&a)== EOF)
             { p=1; break;}
             else
             { if (nb<m)                             /* формируем группу для файла В */
                { fprintf(B," %d ",a);
                k++; nb++; continue;}
               else
                 {fprintf(C," %d ",a);
                  nb=0; nc++; break;
               }
             }
}
if(p)
break;
while (1)
{ if(fscanf(A,"%d",&a)== EOF)
       { p=1;break;
}
else
     { if (nc           {fprintf(C,”%d”,a); k++;
             nc++; continue;
              }
              else
                  {fprintf(B,”%d”,a); k++;
                       nc=0; nb++;
                       break;
                    }
          }
}
if (p)
   break;
}
fclose(A); fclose(B); fclose(C);
vsort2(ff,m);          /* Вызов функции слияния */
if (m>=(k-k/2))          /* конец сортировки */
{     remove (“B”); remove (“C”);
      return 0;
}
m=m*2; k=0;
}
}
/* Фаза слияния */

vsort2(char *a,int m)
/* a - файл для слияния,
          m - число элементов в группах сливаемых файлов В и С */
{ FILE *A,*B,*C; /* файловые переменные */
     int b,c; /* для считывания данных из файлов В и С */
     int nb,nc;/*счетчики считанных из групп элементов файлов В и С*/
     int rb,rc; /* коды завершения операции считывания из файлов В и С*/
if ((A=fopen(a,"w")) == NULL)
     { printf("\n Файл %s не открывается",a);
     getch(); return -1;
     }
if ((B=fopen("B","r")) == NULL)
     { printf("\n Файл B не открывается");
     getch(); return -1;
     }
if ((C=fopen("C","r")) == NULL)
     { printf("\n Файл C не открывается");
      getch(); return -1;
     }
rb= fscanf(B,"%d",&b); rc=fscanf(C,"%d",&c);
nb=1;nc=1;
while(1)
    { if ((rb> 0) && (rc <= 0)) /* конец файла С */
                { fprintf(A," %d ",b);
                while (fscanf(B,"%d",&b) >0)
                fprintf(A," %d ",b);
                     fclose(A); fclose(B); fclose(C);
                return 0;
                }
           else
           { if ((rb ≤ 0) && (rc > 0)) /* конец файла В */
                    { fprintf(A," %d ",c);
               while (fscanf(C,"%d",&c)>0)
                    fprintf(A," %d ",c);
               fclose(A); fclose(B); fclose(C);
                    return 0;
               }
           else
                     if ((rb <= 0) && (rc <= 0))
           /* конец обоих файлов В и С, случается, если они оба пустые */
                     { fclose(A); fclose(B); fclose(C);
                          return 0;
                     }
                }
           if (nb≤m && nc≤m)
               { if (b≤c)
                     { fprintf(A," %d ",b);
                         rb=fscanf(B,"%d",&b);
                         nb++;
                         continue;
                     }
               else
                    { fprintf(A," %d ",c);
                         rc=fscanf(C,"%d",&c);
                    nc++;
                    continue;
                    }
               }
          if (nb≤m && nc>m)
               { fprintf(A," %d ",b);
               rb=fscanf(B,"%d",&b);
               nb++;
               continue;
               }
           if (nb>m && nc≤m)
                    { fprintf(A," %d ",c);
                    rc=fscanf(C,"%d",&c);
                    nc++;
                    continue;
                    }
                if (nb>m && nc>m)
                    { nb=1; nc=1;
                    continue;
               }
   }
}

Для выполнения рассмотренной двухфазной сортировки прямым слиянием нужны 3 файла (3 ленты), поэтому иногда ее называют трехленточным слиянием. Фаза разделения является вспомогательной, в ней записи не переставляются, но она занимает половину всех операций по пересылке записей (чтение из файла А и запись в файлы В и С). Если объединить разделение со слиянием, то от лишних операций можно избавиться. Теперь вместо слияния в одну последовательность результаты слияния сразу же распределяются по двум файлам, которые станут исходными для следующего прохода. Такая сортировка называется однофазной, но она требует наличия 4 файлов, по 2 входных и по 2 выходных при каждом проходе. С учетом этого такую сортировку называют также двухпутевой (балансированной сортировкой. Общее число пересылок при однофазной сортировке М = H*log2«. Число сравнений особого практического значения не имеет, так как затраты на операции пересылок (обмен данными с файлом) намного превышают затраты на сравнение. Рассмотрим пример.
/* ******************************************************* */
/* Сортировка файла прямым слиянием, однофазная сортировка */
/* фаза слияния-разделения выполняется нерекурсивной функцией */
/* 3 вспомогательных файла \vsort21.cpp */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
/* ======================================================= */
main()
{int vsort1(char* r);
int n,b; char f[40]="A";
FILE *fin,*fout;
printf("\n Создание файла А");
if ((fout=fopen(f,"w")) == NULL)
     { printf("\n Файл %s не создан",f);
     getch(); return -1;
     }
n=1024;
printf("\n Исходный файл:\n");
while (n--)
     { b=rand(); /* заполняем файл случайными целыми числами */
     fprintf(fout," %d",b);
      printf("%d\t",b);
     }
fclose(fout);
vsort1(f); /* вызов функции внешней сортировки */
printf("\n Отсортированный файл:\n");
fin=fopen(f,"r");
while (fscanf(fin,"%d",&b) != EOF)
     printf("%d\t",b);
fclose(fin);
getch(); return 0;
}
/* ===================================================== */
/* ВНЕШНЯЯ ОДНОФАЗНАЯ СОРТИРОВКА ПРЯМЫМ СЛИЯНИЕМ,
     фаза начального разделения и вызов фазы слияния-разделения */
int vsort1(char *ff)
/* ff - исходный файл, подлежащий сортировке */
{int vsort2(char *f,int k); /*функция фазы слияния-разделения*/
FILE *A,*B,*C; /* файловые переменные */
     /* файлы "B", "C", "E" в функциях - временные */
int a; /* для чтения из исходного файла */
int nb,nc; /* счетчики элементов в формируемых группах */
int p; /* p=1 - признак достижения конца исходного файла */
     int m=1; /* число элементов в группе: 1,2,4,8,...*/
     int k=0; /*счетчик числа элементов в исходном файле */
while(1)
{ if ((A=fopen(ff,"r")) == NULL)
     { printf("\n Файл %s не открывается",ff);
     getch(); return -1;
     }

if ((B=fopen("B","w")) == NULL)
     { printf("\n Файл B не открывается");
     getch(); return -1;
     }
if ((C=fopen("C","w")) == NULL)
     { printf("\n Файл C не открывается");
      getch(); return -1;
     }
nb=0; nc=0; p=0;
while (1)
    {while (1)
     { if(fscanf(A,"%d",&a) == EOF)
          { p=1; break;
          }
     else
           { if (nb<m) /* формируем группу для файла В */
               { fprintf(B," %d ",a);k++;
                     nb++; continue;
               }
                    else
                    { fprintf(C," %d ",a); k++;
                    nb=0; nc++;
                    break;
               }
          }
     }
     if (p)
     break;
while (1)
     { if(fscanf(A,"%d",&a) == EOF)
          { p=1;break;
           }
     else
          { if (nc<m) /* формируем группу для файла С */
          { fprintf(C," %d ",a); k++;
               nc++; continue;
                }
               else
               {fprintf(B," %d ",a); k++;
                    nc=0;nb++;
                    break;
               }
          }
     }
     if (p)
      break;
}
     fclose(A); fclose(B); fclose(C);
     vsort2(ff,k); /* вызов функции слияния */
     return 0;
m=m*2; k=0;
}
}
/* ====================================================== */
/* ВНЕШНЯЯ ОДНОФАЗНАЯ СОРТИРОВКА ПРЯМЫМ СЛИЯНИЕМ,
     фаза слияния-разделения. Функция нерекурсивная */
vsort2(char *f,int k)
{ FILE *B,*C,*D,*E; /* файловые переменные */
     int b,c; /* для считывания данных из файлов В и С */
     int nb,nc;/*счетчики считанных из групп элементов файлов В и С*/
     int nd,ne; /* счетчики сливаемых в группы элементов */
     int rb,rc; /* коды завершения операции считывания из файлов В и С*/
     int sm; /* число элементов в сливаемой группе: sm=2*m */
     static m=1; /* число элементов в исходной группе */
     static int p=1; /* переключатель */
while(1)
{if(p%2)
{
if ((B=fopen("B","r")) == NULL)
     { printf("\n Файл B не открывается");
     getch(); return -1;
     }
if ((C=fopen("C","r")) == NULL)
     { printf("\n Файл C не открывается");
     getch(); return -1;
     }
if ((D=fopen(f,"w")) == NULL)
     { printf("\n Файл D не открывается");
      getch(); return -1;
     }
if ((E=fopen("E","w")) == NULL)
     { printf("\n Файл E не открывается");
     getch(); return -1;
     }
}
else
{
if ((B=fopen(f,"r")) == NULL)
     { printf("\n Файл D не открывается");
     getch(); return -1;
     }
if ((C=fopen("E","r")) == NULL)
     { printf("\n Файл E не открывается");
     getch(); return -1;
     }
if ((D=fopen("B","w")) == NULL)
     { printf("\n Файл B не открывается");
     getch(); return -1;
     }
if ((E=fopen("C","w")) == NULL)
     { printf("\n Файл C не открывается");
     getch(); return -1;
     }
}
sm=2*m;
rb= fscanf(B,"%d",&b); rc=fscanf(C,"%d",&c);
nb=1;nc=1; nd=0;ne=0;
while(1)
{ if ((rb> 0) && (rc ≤ 0)) /* конец файла С */
          {if (nd<sm) /* формируем группу для файла D */
               { fprintf(D," %d ",b);
                nd++;
               }
           else
          { fprintf(E," %d ",b);
           ne++;
          }
           while (fscanf(B,"%d",&b) >0)
                { if (nd<sm) /* формируем группу для файла D */
               { fprintf(D," %d ",b);
                     nd++;
                }
               else
               { fprintf(E," %d ",b);
                          ne++;
                     }
                }
               fclose(B); fclose(C);
           break;
          }
          else
          { if ((rb ≤ 0) && (rc > 0)) /* конец файла В */
               { if (nd<sm) /* формируем группу для файла D */
               { fprintf(D," %d ",c);
                nd++;
               }
           else
               { fprintf(E," %d ",c);
                ne++;
               }
          while (fscanf(C,"%d",&c)>0)
               { if (nd<sm) /* формируем группу для файла
D */
                          { fprintf(D," %d ",c);
                         nd++;
                     }
                    else
                     { fprintf(E," %d ",c);
                    ne++;
                }
               }
               fclose(B); fclose(C);
          break;
          }
     else
               if ((rb ≤ 0) && (rc ≤ 0)) /* конец обоих файлов В и С,

               случается, если они оба пустые */
               { fclose(B); fclose(C);
                    break;
               }
          }
      if (nb≤m && nc≤m)
               { if (b≤c)
               { if (nd==sm && ne==sm)
                    { nd=0; ne=0;
                     }
                    if (nd<sm) /* формируем группу для файла D */
                    { fprintf(D," %d ",b);
                          nd++;
                     }
                    else
                    { fprintf(E," %d ",b);
                          ne++;
                     }
                    rb=fscanf(B,"%d",&b);
                    nb++;
                    continue;
                }
           else
               { if (nd==sm && ne==sm)
                    { nd=0; ne=0;
                     }
                    if (nd                    { fprintf(D," %d ",c);
                          nd++;
                     }
                    else
                    { fprintf(E," %d ",c);
                          ne++;
                    }
                    rc=fscanf(C,"%d",&c);
                    nc++;
                    continue;
                }
          }
      if (nb≤m && nc>m)
          { if (nd==sm && ne==sm)
               { nd=0; ne=0;
                }
                if (nd<sm) /* формируем группу для файла D */
                { fprintf(D," %d ",b);
                     nd++;
               }
                    else
                    { fprintf(E," %d ",b);
                          ne++;
                    }
                rb=fscanf(B,"%d",&b);
          nb++;
          continue;
          }
     if (nb>m && nc≤m)
          { if (nd==sm && ne==sm)
                { nd=0; ne=0;
                }
          if (nd<sm) /* формируем группу для файла D */
                { fprintf(D," %d ",c);
                     nd++;
                }
           else
                { fprintf(E," %d ",c);
                     ne++;
                }
          rc=fscanf(C,"%d",&c);
          nc++;
          continue;
          }
      if (nb>m && nc>m)
          { nb=1; nc=1;
           continue;
          }
} /* конец цикла */
          fclose(B); fclose(C); fclose(D); fclose(E);
if (m≥(k-k/2))
     { if (!(p%2))
          { remove(f);
                     rename("B",f);
          }
          remove("B"); remove("C");remove("E");
          return 0;
     }
      m=2*m;
      p++;
}
}