Внешняя сортировка (сортировка последовательностей)

ОП не помещается приходится использовать внешние файлы. Исходный набор данных

хранится во внешнем файле и многократно должен считываться в ОП. В каждый момент времени в ОП находится лишь часть полного набора. Главным критерием при разработке методов сортировки становится минимизация числа обращений к внешней памяти.
Основой большинства алгоритмов внешней сортировки является принцип слияния двух упорядоченных последовательностей в единый упорядоченный набор.

разбивается на две половины В и С.
2. Части В и

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

из файла А разбиваются на две равные части(при нечетном числе

записей в первой части на 1 больше) и помещаются в файлы В и С соответственно

Файл А

Файл В

Файл С

Файл А

Файл В

Файл С

Фаза разделения

Фаза слияния

Фаза слияния – данные из файлов В и С, слитые в упорядоченные пары, четверки, восьмерки и т.д., помещаются в файл А.

файлы В и С как выходные (для записи)
3. Считываемые из

файла А записи попеременно посылаются в файлы В и С

4. Закрыть файлы А, В, С.

файлы В и С как входные (для чтения)
3. Установить размер

порции сливаемых записей = 1

Для каждой порции считываются по одной записи из файлов В и С

5. Меньшая из них пересылается в файл А, и считывается очередная запись из того файла, чья запись была переслана в файл А

2 < 8

4 < 8

6 < 8

8<11

11<13

7<13

10<13

12<13

6. Закрыть файлы А, В, С.

файлы В и С как выходные (для записи)
3. Считываемые из

файла А записи попеременно посылаются в файлы В и С: первая запись в файл В, вторая в С, затем третья в В, четвертая в С и т.д.
4. Закрыть файлы А, В и С.

файлы В и С как входные (для чтения)
3. Установить размер

порции сливаемых записей (эти порции равны 1, 2, 4, … записям для первого и последующих этапов соответственно).
4. Для каждой порции считываются по одной записи из файлов В и С.
5. Меньшая из них пересылается в файл А, и считывается очередная запись из того файла, чья запись была переслана в файл А.

записи очередной одного из файлов не будут исчерпаны.
7. Оставшиеся записи

из порции другого файла пересылаются в файл А.
8. Пункты 4-7 повторяются до тех пор, пока не будет достигнут конец одного из файлов В или С. Тогда оставшиеся записи из другого файла пересылаются в файл А.
9. Закрытие файлов А, В и С.

Сортировка завершается тогда, когда длина порции достигнет n

(ключи).
//-------------------------------------------
#include
#include
#include
//-------------------------------------------
int main()
{ int vsort1(char* r);
int n,b;

char f[40]="A";
FILE *fin, *fout;
printf("\n Sozdanie file A");
if((fout=fopen(f,"w"))==NULL)
{printf("\n File %s not create",f);
getch();
return -1;
}

случайными числами
fprintf(fout,"%d ",b);
printf("%d\t",b);
}
fclose(fout);
vsort1(f);

//вызов функции внешней сортировки
printf("\n Otsortirovanni file:\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 p; //р=1 – признак достижения конеца исходного файла
int m=1; //число элементов в группе: 1,2,4,8,…
int k=0; //счетчик числа элементов в исходном файле
while(1)
{ if ( (A=fopen(ff,"r"))==NULL)
{ printf("\n File %s not open",ff); //Проверка на открытие файла
getch(); return -1; }
if ( (B=fopen("B","w"))==NULL)
{printf("\n File B1 not open");
getch(); return -1; }
if ( (C=fopen("C","w"))==NULL)
{printf("\n File C1 not open");
getch(); return -1; }

{ if(fscanf(A,"%d",&a)==EOF)
{ p=1;

break; }
else
{ if(nbдля файла В */
{ 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для файла С*/
{ fprintf(C, "%d ",a);
k++; nc++;
continue;
}
else
{ fprintf(B, "%d ",a);
k++; nc=0;
nb++; break;
}
}
}

слияния
if (m>=(k-k/2)) //конец сортировки
{ remove("B");

//удаление вспомогательных файлов
remove("C");
return 0;
}
m=m*2; //увеличиваем число элементов в группе
k=0;
}
}

число элементов в сливаемых группах */
{ FILE *A, *B, *C;

//файловые переменные
int b,c; //для считывания данных из файлов В и С
int nb,nc; //счетчики считанных из групп элементов файлов В и С
int rb,rc; //коды завершения операции считывания из файлов В и С
if((A=fopen(a,"w"))==NULL) //Проверка на открытие файлов
{printf("\n File %s not open",a);
getch(); return -1;
}
if((B=fopen("B","r"))==NULL)
{printf("\n File B not open");
getch(); return -1;
}
if((C=fopen("C","r"))==NULL)
{printf("\n File C not open");
getch(); return -1;
}

Внешняя двухфазная сортировка прямым слиянием, фаза слияния

С
{ 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)) /*конец обоих файлов В и С случается, если они оба пустые*/
{ fprintf(A, "%d ",c);
fclose(A); fclose(B); fclose(C);
return 0;
} }

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; }
}
}

последовательность результаты слияния сразу же распределяются по двум файлам, которые

станут исходными для следующего прохода. Она требует наличия 4 файлов, по 2 входных и по 2 выходных, при каждом проходе. Такую сортировку также называют двухпутевой сбалансированной сортировкой. Общее число пересылок при однофазной сортировке М=n*log2n.

слияния-разделения
Файл В
Файл С
Файл А
Заключительный этап

char f[40]="A";
FILE *fin, *fout;
printf("\n Sozdanie file A");
if

((fout=fopen(f,"w"))==NULL)
{ printf("\n File %s not create",f);
getch();
return -1;
}

Пример однофазной сортировки прямым слиянием.

n=100;
printf("\n Ishodni file:\n");
while(n--)
{ b=rand(); /*Заполняем файл случайными целыми числами*/
fprintf(fout, "%d ",b);
printf("%d\t",b);
}
fclose(fout);
vsort1(f);
printf("\n Otsortirovani file:\n");
fin=fopen(f,"r");
while (fscanf(fin,"%d",&b)!=EOF)
printf("%d\t",b);
fclose(fin);
getch(); return 0;
}

*f,int k); //функция фазы слияния-разделения
FILE *A, *B, *C; //файловые переменные
int

a; //для чтения из исходного файла
int nb,nc; //счетчики элементов в формируемых группах
int p; //признак достижения конца исходного файла
int m=1; //число элементов в группе: 1,2,4,8…
int k=0; //счетчик числа элементов в исходном файле
while(1)
{ if((A=fopen(ff,"r"))==NULL)
{ printf("\n File %s not open",ff);
getch(); return -1; }
if((B=fopen("B","w"))==NULL)
{ printf("\n File B not open");
getch(); return -1; }
if((C=fopen("C","w"))==NULL)
{ printf("\n File C not open");
getch(); return -1; }

Внешняя однофазная сортировка прямым слиянием, фаза начального разделения и вызов фазы слияния-разделения

{ p=1; break;
}
else

{ if(nb { 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 { 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;
} }

файловые переменные
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 File B not open");
getch(); return -1; }
if((C=fopen("C","r"))==NULL) {printf("\n File C not open");
getch(); return -1; }
if((D=fopen(f,"w"))==NULL) { printf("\n File D not open");
getch(); return -1; }
if((E=fopen("E","w"))==NULL) { printf("\n File E not open");
getch(); return -1; } }

Внешняя однофазная сортировка прямым слиянием, фаза слияния-разделения

not open");
getch();
return

-1;
}
if((C=fopen("E","r"))==NULL)
{printf("\n File E not open");
getch();
return -1;
}
if((D=fopen("B","w"))==NULL)
{printf("\n File B not open");
getch();
return -1;
}
if((E=fopen("C","w"))==NULL)
{printf("\n File C not open");
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 { fprintf(D,"%d ",b);
nd++; }
else
{ fprintf(E,"%d ",b);
ne++; }
while(fscanf(B, "%d", &b)>0)
{ if (nd { fprintf(D, "%d ",b);
nd++; }
else
{ fprintf(E, "%d ",b);
ne++; } }
fclose(B); fclose(C); break; }

B
{ if (nd

{ fprintf(D, "%d ",c); nd++; }
else
{ fprintf(E, "%d ",c); ne++; }
while(fscanf(C,"%d", &c)>0)
{ if(nd { 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 { 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++; }
c=fscanf(C,"%d",&c);
nc++; continue; } }

ne==sm)
{ nd=0; ne=0;

}
if (nd { 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 { 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=1;
}
}

(серии), называется естественным слиянием.

записи с ключами:
А:
17
31
5
59
13
41
43
67
11
23
71
29
47
3
7
2
19
57
Выделим серии, которые для наглядности разделим знаками |
Разобьем

файл А на два файла В и С: первую серию запишем в файл В, вторую в файл С, третью в файл В, четвертую в файл С и т.д., которые затем сольем в файл А.

В:

С:

текущей серии из файла В
Проверка на исчерпанность текущей серии из

файла С

59 ≥ 5

17 < 59

31 ≥ 17

31 < 59

13 ≥ 31

13 ≥ 13

11 ≥ 11

11 < 13

23 ≥ 11

13 < 23

41 ≥ 13

23 < 41

29 ≥ 23

29 < 41

47 ≥ 29

41 < 47

43 ≥ 41

43 < 47

67 ≥ 43

47 < 67

2 ≥ 47

2 ≥ 2

3 ≥ 3

2 < 3

19 ≥ 2

3 < 19

7 ≥ 3

7 < 19

71 ≥ 7

19 < 71

57 ≥ 19

57 < 71

Конец файла С !

Открыть файлы В и С как выходные (для записи).
3. Считывать

записи и посылать их в файл В до тех пор, пока очередная запись больше предыдущей (ri > ri-1), то есть до конца серии.
4 Запись ri <= ri-1 записать в файл С. Считывать записи и посылать их в С до тех пор, пока ri > ri-1, то есть до конца следующей серии.
5. Выполнять пункты 3 и 4, пока не будет достигнут конец файла А.
6. Выполнить фазу слияния файлов В и С в файл А.
7. Пункты 1-5 повторять до тех пор, пока в результате слияния в выходной файл не будет записана только одна-единственная серия

из файла А при разделении образуют в выходном файле В

или С одну серию, в таком случае число проходов уменьшается.
Пусть в файле А находятся 6 серий:

А:

1…29

21…47

31…55

49…81

75…80

3…18

При разделении в файлы В и С попадут серии в следующем порядке:

В:

1…29

31…55

75…80

С:

21…47

49…81

3…18

В файле В три серии образовали одну серию

1…80

В файле С первые две серии объединились в одну.

21…81

объединить в одну фазу. Для этого достаточно полученные при слиянии

файлов В и С серии поочередно направлять в файлы D и E, и, наоборот, если сливаются серии из файлов D и Е, полученные серии поочередно направлять в В и С.

Сортировка заканчивается, если при очередной фазе слияния-разделения образуется только одна серия и один из выходных файлов останется пустым, т.е. туда не будет записана ни одна серия.

vnsort1(char* r); int n,b; char f[40]="A"; FILE

*fin, *fout;
printf("\n Create file A");
if ((fout=fopen(f,"w"))==NULL)
{ printf("\n File %s not create",f); getch(); return -1; }
n=327; printf("\n Ishodni file\n");
while (n--)
{ b=rand(); //заполняем файл случайными числами
fprintf(fout,"%d ",b); printf("%d\t",b); }
fclose(fout);
vnsort1(f); //вызов функции внешней сортировки
printf("\n Otsortirovani file:\n"); fin=fopen(f,"r");
while(fscanf(fin,"%d",&b)!=EOF) printf("%d\t",b);
fclose(fin); getch(); return 0; }

int vnsort2(char *f); //функция фазы слияния
FILE *A, *B,*C; //

файловые переменные
int a1,a2; //для чтения из исходного файла
int pb,pc; //признаки записи в файлы разделения
int p; //р=1 – признак достижения конеца исходного файла
while(1) //цикл 1 – цикл повторения фаз разделения и слияния
{ if((A=fopen(ff,"r"))==NULL)
{ printf("\n File not open",ff);
getch(); return -1; }
if((B=fopen("B","w"))==NULL)
{ printf("\n File B not open");
getch(); return -1;
}
if((C=fopen("C","w"))==NULL)
{ printf("\n File C not open");
getch(); return -1;
}

Внешняя двухфазная сортировка естественным слиянием, фаза разделения и вызов фазы слияния

if(fscanf(A,"%d",&a1)==EOF)
{ printf("\nSortiruemi file pustoi");

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
} } }

2
while(1)

//цикл 4, цикл формирования серии в файле C
{ if(fscanf(A,"%d",&a2)==EOF)
{ p=1;
break; //выход из цикла 4
}
else
{ if(a2>=a1) //запишем в серию в файле C
{ 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 rb,rc; //коды

завершения операции считывания из файлов В и С
// Подготовительные операции
if((A=fopen(a,"w"))==NULL)
{ printf("\n File not open",a);
getch(); return -1;
}
if((B=fopen("B","r"))==NULL)
{ printf("\n File B not open");
getch(); return -1;
}
if((C=fopen("C","r"))==NULL)
{ printf("\n File C not open");
getch(); return -1;
}

Внешняя двухфазная сортировка естественным слиянием, фаза слияния

файла С*/
{ 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)) /*конец файла В*/
{ 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=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=c2; BB:fprintf(A,"%d ",b2); b1=b2; rb=fscanf(B,"%d",&b2);
if(rb<=0) continue;
if(b2>=b1) goto BB; else { b1=b2; continue; }
}
if(b2=c1) //текущая серия из файла В исчерпана
{ b1=b2; CC:fprintf(A,"%d ",c2);
c1=c2; rc=fscanf(C,"%d",&c2);
if(rc<=0) continue;
if(c2>=c1) goto CC;
else
{ c1=c2; continue; }
} } }

они поровну распределяются в N файлов, то первый проход даст

n/N серий, второй проход - , третий - и т.д.
Отсюда общее число проходов, необходимых для сортировки п элементов с помощью N-путевого слияния, равно к — logNn, а число пересылок при объединении фаз слияния и разделения в самом худшем случае будет М = nlogNn. При каждом проходе будут участвовать N входных и N. выходных файлов, в которые по очереди распределяются последовательные серии.

5
Серия 2
Серия 6
Серия 3
Серия 7
Серия 4
Серия 8
Входной файл
Файл 1
Выходные файлы
Файл

2

Файл 3

Файл 4

Первоначально:

активен, если не исчерпаны записи текущей j-й серии файла;
2) файл

временно не активен, если исчерпаны записи текущей j-й серии, но не достигнут конец файла. Такой файл не участвует в процессе слияния очередной серии, но активизируется при слиянии следующей серии;
3) файл не активен, если достигнут конец файла, т.е. исчерпаны все серии. В текущем проходе такой файл больше не используется.

Для определения конца текущей серии или конца файла может потребоваться опережающее чтение записи или ведение специальной таблицы.

Выходные файлы становятся входны­ми, а входные файлы - выходными, и

начинается очередной Проход сортировки.
Процесс сортировки заканчивается, когда при очередном проходе будет сформирована одна-единственная серия

несколько входных файлов с разным числом серий и только один

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

коротких. Поэтому его нецелесообразно применять с самого начала сортировки, поскольку

для случайного входного набора на первых шагах будут получаться очень короткие серии, что приведет к неоправданно большому числу обращений к дисковой памяти.
Для устранения этого недостатка можно поступить следующим образом:
исходный сверхбольшой набор данных разделяется на отдельные фрагменты такого размера, чтобы каждый фрагмент мог целиком разместиться в ОП
каждый фрагмент отдельно загружается в ОП и сортируется каким-нибудь классическим улучшенным методом (например – алгоритмом быстрой сортировки)
каждый отсортированный фрагмент рассматривается как серия и сохраняется во вспомогательном файле; в простейшем случае достаточно двух вспомогательных файлов, в которые серии сбрасываются поочередно (нечетные серии – в один файл (A), четные – в другой (B)).
Эти действия носят подготовительный характер.

1
Фрагмент 2
Фрагмент 3
Фрагмент 4
Фрагмент 5
Фрагмент 6
Серия 1
Файл А
Серия 3
Серия 5
Серия

1

Файл А

Серия 3

Серия 5

Серия 2

Файл В

Серия 4

Серия 6

разных файлов, т.е. серий 1 и 2, и результат записывается

в третий вспомогательный файл С
выполняется объединение вторых серий из разных файлов, т.е. серий 3 и 4, и результат записывается во вспомогательный файл D
выполняется объединение третьих серий из разных файлов, т.е. серий 5 и 6, и результат записывается опять в файл С
серии 7 и 8 после объединения записываются в файл D и т.д.
В итоге, в файлах С и D получатся объединенные серии, которые потом между собой начинают попарно объединяться с записью результата во вспомогательные файлы А и В и т. д. Процесс укрупнения серий продолжается до тех пор, пока не будет получена одна единственная серия, представляющая полученный результат.

С
Серия 5+6
Серия 3+4
Файл D
Серия 1+2+3+4
Серия 5+6
Серия
1+2+3+4+5+6
Процесс укрупнения серий