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

Содержание

Введение. 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);

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

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