/* двухфазная сортировка, параметр - имя файла*/
int vnsort1(char *ff); // фаза разделения серий
int vnsort2(char *a); // фаза слияния
int vnsort1( char *ff )
{
FILE *A,*B,*C; /* файловые переменные */
/* файлы "B", "C" в функциях - временные */
int a1,a2; /* для чтения из исходного файла */
int pb,pc; /* признаки записи в файлы разделения */
int p; /* p=1 - признак достижения конца исходного файла */
while(1) /* цикл 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;
}
p = 0;
pb = 0;
pc = 0;
if(fscanf(A, "%d", &a1) == EOF)
{
printf("\n Сортируемый файл - пустой");
getch();
return -1;
}
else
{
fprintf(B, " %d", a1);
pb=1;
}
while(1) /* цикл 2, цикл формирования серий в файлах В и С */
{
while (1) /* цикл 3, цикл формирования серии в файле В */
{
if(fscanf(A, "%d", &a2) == EOF)
{
p=1; break; /* выход из цикла 3 */
}
else
{
if (a2>=a1) /* запишем в серию в файле В */
{
fprintf(B, " %d", a2);
a1=a2;
pb=1;
continue;
}
else /* запишем первую запись новой серии в файле С */
{
fprintf(C, " %d", a2);
a1=a2;
pc=1;
break; /* выход из цикла 3 */
}
}
}
if (p)
break; /* выход из цикла 2 */
while (1) /* цикл 4, формирование серии в файле С */
{
if(fscanf(A, "%d", &a2) == EOF)
{
p=1;
break; /* выход из цикла 4 */
}
else
{
if (a2 >= a1) /* запишем в серию в файле С */
{
fprintf(C, " %d", a2);
a1=a2;
pc=1;
continue;
}
else
{
fprintf(B, " %d", a2);
a1=a2;
pb=1;
break; /* выход из цикла 4 */
}
}
}
if (p)
break; /* выход из цикла 2 */
}
fclose(A);
fclose(B);
fclose(C);
if (pb && pc) /* исходный файл записан в оба файла разделения */
vnsort2(ff); /* вызов функции слияния */
else
{ /* Удаление вспомогательных файлов */
remove("B"); remove("C");
return 0; /* конец сортировки */
}
}
}
int vnsort2(char *a)
{
bool flag;
FILE *A,*B,*C; /* файловые переменные */
int b1,b2,c1,c2; /* для считывания данных из файлов В и С */
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", &b2);
rc=fscanf(C,"%d",&c2);
b1=b2;
c1=c2;
while (1)
{
if ( (rb > 0) && (rc <= 0) ) // файл С закончился
{
fprintf(A," %d",b2);
while (fscanf(B,"%d",&b2) >0)
fprintf(A," %d",b2);
fclose(A);
fclose(B);
fclose(C);
return 0;
}
else if ( (rb <= 0) && (rc > 0) ) // файл B закончился
{
fprintf(A," %d",c2);
while (fscanf(C,"%d",&c2) >0)
fprintf(A," %d",c2);
fclose(A);
fclose(B);
fclose(C);
return 0;
}
else if ( (rb <= 0) && (rc <= 0) ) // оба файла закончились
{
fclose(A);
fclose(B);
fclose(C);
return 0;
}
if ( (b2 >= b1) && (c2 >= c1) ) /* обе сливаемые серии не исчерпаны */
{
if (b2 <= c2)
{
fprintf(A," %d",b2); b1=b2;
rb=fscanf(B,"%d",&b2);
continue;
}
else
{
fprintf(A," %d",c2);
c1=c2;
rc=fscanf(C,"%d",&c2);
continue;
}
}
if ( (b2 >= b1) && (c2 < c1) ) // серия файла C кончилась
{
c1 = c2;
flag = false;
do
{
fprintf(A," %d",b2);
b1 = b2;
rb = fscanf(B,"%d",&b2);
if( rb <= 0 )
{
flag = true;
break;
}
if( b2 < b1 )
{
b1 = b2;
flag = true;
break;
}
if ( flag == true )
break;
} while(1);
if( flag == true )
continue;
}
if ( (b2 < b1) && (c2 >= c1) ) // серия файла B кончилась
{
b1 = b2;
flag = false;
do
{
fprintf(A," %d",c2);
c1 = c2;
rc = fscanf(C,"%d",&c2);
if( rc <= 0 )
{
flag = true;
break;
}
if( c2 < c1 )
{
c1 = c2;
flag = true;
break;
}
if ( flag == true )
break;
} while (1);
if( flag == true )
continue;
}
}
}
[C/C++ или алгоритм] Сортировка двухфазным слиянием
Вот здесь есть алгоритм сортировки слиянием, но он по идее однофазный... поискал в гугле, нашёл небольшое описание двухфазного слияния, но встал вопрос как искать наиболее упорядоченную последовательность...
киньте в меня нормальным линком с теорией, или кодом (желательно с описанием времени, занимаемой памяти и сложности)
http://cavernxxx.by.ru/i-4-4/struct/sort.htm - код на Си (сортировка файла естественным слиянием - двухфазная сортировка;
сортировка файла прямым слиянием - двухфазная сортировка)
http://lothar.nm.ru/infa/doc/%cb%e5%ea%f6%e8%ff%20%ee%f2%20291004.doc - описание двухфазной сортировки внутренней и внешней, код
http://www.dore.ru/perl/nntp.pl?f=1&gid=17&mid=62765 - пункты 'Сортировка простым слиянием' и 'Сортировка естественным слиянием' - описание принципа.
Или Вам не это нужно?
ага, спасибо) репу кинул
я вот думаю... почему однофазная сортировка реализована через рекурсивный алгоритм, а двух/многофазная через бесконечный цикл? суть я понял, но вот вопрос... если сложность однофазного слияния nlogn, то двухфазного получается колеблется до n(logn+1) в худшем случае... памяти используется столько же, где тут получается выигрыш в быстродействии? или я неправильно понял алгоритм?
Цитата: Mr.Hacker
где тут получается выигрыш в быстродействии?
Вообще-то, насколько я понимаю, все наоборот - однофазная сортировка является улучшением двухфазной (по быстродействию) за счет объединения фаз слияния и разделения, а вот памяти однофазная сортировка занимает больше, так как требует больше дополнительных файлов.
в-общем, я написал, использовав частично код с