Сортировка файлов естественным слиянием

Содержание

Введение. 4

1 Анализ алгоритмов сортировок. 6

1.1 Понятие сортировки. 6

1.2 Основные понятия внешних сортировок. 7

1.3 Сортировка простым слиянием. 10

1.4 Сортировка естественным слиянием. 11

1.5 Оценка сложности алгоритма. 13

2 Проектирование программного средства. 15

2.1 Описание работы программы.. 15

2.2 Руководство пользователя. 15

2.3 Тестирование программного средства. 16

Заключение. 19

Список использованной литературы.. 20

Приложение А.. 21

Приложение А

(программный код)

#include <iostream>

#include <stdlib.h>

#include <time.h>

#include <windows.h>

using namespace std;

//вывод содержимого файла

void Print_File(char *name){

int c;

FILE *x;

x = fopen(name,"r");

while(!feof(x)){

fscanf(x,"%d",&c);

cout<<c<<" ";

}

fclose(x);

cout<<endl<<endl;

}

//определение конца блока

bool End_Range (FILE * f){

int tmp;

tmp = fgetc(f);

tmp = fgetc(f);

if (tmp != '\'') fseek(f,-2,1);

else fseek(f,1,1);

return tmp == '\'' ? true : false;

}

//Описание функции сортировки естественным слиянием

int Natural_Merging_Sort(char *name){

int s1, s2, a1, a2, mark, count;

FILE *f, *f1, *f2; //объявляем файловые переменные

s1 = s2 = 1;

count=0; //колво фаз

while ( s1 > 0 && s2 > 0 ){ //условие выхода - отсортированая последовательность

mark = 1;

count++;

s1 = 0;

s2 = 0;

f = fopen(name,"r"); //открываем файл для чтения

f1 = fopen("nmsort_1","w"); //открываем 2 файла для записи и начинаем распределение чисел

f2 = fopen("nmsort_2","w");

fscanf(f,"%d",&a1); //считываем первое число

if ( !feof(f) ) {

fprintf(f1,"%d ",a1); //записывем число в первый файл

}

if ( !feof(f) ) fscanf(f,"%d",&a2); //считываем второе число

while ( !feof(f) ){

if ( a2 < a1 ) { //если серия закончилась

switch (mark) { //маркер конца серии

case 1:{fprintf(f1,"' "); mark = 2; s1++; break;} //если серия закончилась то маркером меняем файл в который идет запись

case 2:{fprintf(f2,"' "); mark = 1; s2++; break;}

}

}

if ( mark == 1 ) { fprintf(f1,"%d ",a2); s1++; } //запись в файл

else { fprintf(f2,"%d ",a2); s2++;}

a1 = a2;

fscanf(f,"%d",&a2); //считываем следующее число

}

if ( s2 > 0 && mark == 2 ) { fprintf(f2,"'");}

if ( s1 > 0 && mark == 1 ) { fprintf(f1,"'");}

fclose(f2); //закрываем файлы

fclose(f1);

fclose(f);

............ и т д

Описание + программа