Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Сортировка файлов

Поиск:
Сортировка файлов


Straight merge

Код

//////////////////////////////////////////////////////////////////////////////
//
//  File sort (straight merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp, 4.tmp
//   We use four files to sort given sequence of data.
//     1) Split file into 2 parts (A and B)
//     2) Combine A and B to C, sorting 2-element groups
//     3) Repeat these steps for file C, sorting 4-element groups,
//        8-elements,... while size of group less than file size.
//     We can optimize this method by uniting splitting and combining:
//     we just need to change destination on each step: combine one
//     group to C another to D, next group again to C and so on
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

int copy(FILE *A, FILE *B, FILE *C, int n)
{
  int a,b,q,r,m=0;

  q=r=0;
  // combining to C
  if (!feof(A)) fread(&a,sizeof(int),1,A);
  if (!feof(B)) fread(&b,sizeof(int),1,B);
  while (!feof(A) && !feof(B) && q<n && r<n)
  {
    if (a<b)
    {
      fwrite(&a,sizeof(int),1,C);m++;q++;
      if (q<n) fread(&a,sizeof(int),1,A);
    }
    else
    {
      fwrite(&b,sizeof(int),1,C);m++;r++;
      if (r<n) fread(&b,sizeof(int),1,B);
    }
  }
  // writing remainders
  while (!feof(A) && q<n)
  {
    fwrite(&a,sizeof(int),1,C);m++;q++;
    if (q<n) fread(&a,sizeof(int),1,A);
  }
  while (!feof(B) && r<n)
  {
    fwrite(&b,sizeof(int),1,C);m++;r++;
    if (r<n) fread(&b,sizeof(int),1,B);
  }

  return m;
}

void main(void)
{
  FILE *A,*B,*C,*D,*input,*output;
  int N=0,c,m,p,l;

  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  l=0;
  A=fopen("1.tmp","w+b");
  B=fopen("2.tmp","w+b");
  C=fopen("3.tmp","w+b");
  D=fopen("4.tmp","w+b");


  // reading from source and splitting data into A & B
  while (!feof(input))
  {
    fscanf(input,"%d ",&c);
    fwrite(&c,sizeof(int),1,(N%2==0?A:B));
    N++;
  }
  rewind(A);
  rewind(B);

  p=1;
  while (p<N)
  {
    m=N;
    while (m!=0)
    {
      // uniting splitting and combining
      // here we combine from A and B to C and D
      m-=copy(A,B,C,p);
      m-=copy(A,B,D,p);
    }
    // swap A,B and C,D
    // now we'll combine from C and D and split to A and B
    fclose(A);
    fclose(B);
    fclose(C);
    fclose(D);
    A=fopen((l?"1.tmp":"3.tmp"),"rb");
    B=fopen((l?"2.tmp":"4.tmp"),"rb");
    C=fopen((!l?"1.tmp":"3.tmp"),"wb");
    D=fopen((!l?"2.tmp":"4.tmp"),"wb");
    l=!l;
    // groups will be larger twice
    p*=2;
  }

  fread(&c,sizeof(int),1,A);
  while (!feof(A))
  {
    fprintf(output,"%d ",c);
    fread(&c,sizeof(int),1,A);
  }

  fclose(A);
  fclose(B);
  fclose(C);
  fclose(D);
  fclose(input);
  fclose(output);
}



Natural merge

Код

//////////////////////////////////////////////////////////////////////////////
//
//  File sort (natural merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use three files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into parts A and B, writing first
//      series from C to A, second one to B, third - to C, and so on
//   2) Combine files A and B into C, sorting distributed series
//   3) Repeat first two steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

void main(void)
{
  FILE *A,*B,*C,*input,*output;
  int sorted,a,b,c,old;

  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  A=fopen("1.tmp","w+b");
  B=fopen("2.tmp","w+b");
  C=fopen("3.tmp","w+b");

  // reading from source and copying data into C
  while (!feof(input))
  {
    fscanf(input,"%d ",&c);
    fwrite(&c,sizeof(int),1,C);
  }
  rewind(C);

  do
  {
    // reopeneing files A and B
    fclose(A);
    fclose(B);
    A=fopen("1.tmp","w+b");
    B=fopen("2.tmp","w+b");
    rewind(C);

    // distributing series from C to A and B
    fread(&c,sizeof(int),1,C);
    sorted=1;
    while (!feof(C))
    {
      // series to A
      do
      {
         old=c;
         fwrite(&c,sizeof(int),1,A);
         fread(&c,sizeof(int),1,C);
      } while (!feof(C) && old<=c);
      old=c;
      // series to B
      while (!feof(C) && old<=c)
      {
        old=c;
        fwrite(&c,sizeof(int),1,B);
        fread(&c,sizeof(int),1,C);
        sorted=0; // if there are more than 1 series then sequence isn't sorted
      }
    }
    // reopening file C
    fclose(C);
    C=fopen("3.tmp","w+b");
    rewind(A);
    rewind(B);
    // combining A and B back to C
    fread(&a,sizeof(int),1,A);
    fread(&b,sizeof(int),1,B);
    while (!feof(A) && !feof(B))
    {
      if (a<b)
      {
        old=a;
        fwrite(&a,sizeof(int),1,C);
        fread(&a,sizeof(int),1,A);
        if (feof(A) || a<old)
        do
        {
          old=b;
          fwrite(&b,sizeof(int),1,C);
          fread(&b,sizeof(int),1,B);
        } while(!feof(B) && b>=old);
      }
      else
      {
        old=b;
        fwrite(&b,sizeof(int),1,C);
        fread(&b,sizeof(int),1,B);
        if (feof(B) || b<old)
        do
        {
          old=a;
          fwrite(&a,sizeof(int),1,C);
          fread(&a,sizeof(int),1,A);
        } while(!feof(A) && a>=old);
      }
    }

    // copying remainder from A (or B) to C
    while (!feof(A))
    {
      fwrite(&a,sizeof(int),1,C);
      fread(&a,sizeof(int),1,A);
    }
    while (!feof(B))
    {
      fwrite(&b,sizeof(int),1,C);
      fread(&b,sizeof(int),1,B);
    }
  } while (!sorted);  // sort until there will be only one series

  // writing sorted sequence
  rewind(C);
  fread(&c,sizeof(int),1,C);
  while (!feof(C))
  {
    fprintf(output,"%d ",c);
    fread(&c,sizeof(int),1,C);
  }

  // closing all opened files
  fclose(A);
  fclose(B);
  fclose(C);
  fclose(input);
  fclose(output);
}



Balanced merge

Код

//////////////////////////////////////////////////////////////////////////////
//
//  File sort (balanced merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use N files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into N files, writing first
//      series from C to F1, second one to F2, third - to F3, and so on
//   2) Combine files F1,F2,F3,...,Fn, sorting distributed series
//   3) Repeat first two steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N    10  // number of temporary files (must be even and greater than 2)
#define Nh    N/2 // must be an integer

struct ExtFile
{
  FILE *F;
  int first; // current element of this file
  char eor; // indicates end of series
};

// this function copies data element from x to y, updating (.first) members
void copy(ExtFile *x, ExtFile *y)
{
  y->first=x->first;
  fwrite(&y->first,sizeof(int),1,y->F);
  fread(&x->first,sizeof(int),1,x->F);
  x->eor=x->first<y->first;
}

void main(void)
{
  FILE *input,*output;
  ExtFile F[N];
  int l,old,j,mx,tx,min,x,t[N],ta[N],k1,k2;
  char name[13];

  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  for (int i=0;i<N;i++)
  {
    gcvt(i,8,name);
    strcat(name,".tmp");
    F[i].F=fopen(name,"w+b");
    F[i].eor=0;
  }

  // distributing given data
  j=Nh;
  l=0;
  fscanf(input,"%d ",&x);
  while (!feof(input))
  {
    if (j<Nh-1) j++; else j=0;
    do
    {
      old=x;
      fwrite(&x,sizeof(int),1,F[j].F);
      fscanf(input,"%d ",&x);
    } while (!feof(input) && x>=old);
    l++;
  }
  if (x<old)
  {
    if (j<Nh-1) j++; else j=0;
    l++;
  }
  fwrite(&x,sizeof(int),1,F[j].F);

  for (i=0;i<N;i++) t[i]=i;

  do
  {
    // merging t[0]..t[Nh-1] to t[Nh]..t[N-1]
    if(l<Nh) k1=l-1; else k1=Nh-1;
    for(i=0;i<=k1;i++)
    {
      rewind(F[t[i]].F);
      ta[i]=t[i];
      fread(&F[t[i]].first,sizeof(int),1,F[t[i]].F);
    }
    l=0; // number of input series
    j=Nh; // index of input sequence
    // merging input series to t[j]
    do
    {
      l++;
      k2=k1;
      // selecting minimal element from F1..Fn
      do
      {
        i=1;
        mx=0;
        min=F[ta[0]].first;
        while (i<=k2)
        {
          x=F[ta[i]].first;
          if(x<min)
          {
            min=x;
            mx=i;
          }
          i++;
        }
        copy(&F[ta[mx]],&F[t[j]]);
        if (feof(F[ta[mx]].F))
        {
          // excluding file
          fclose(F[ta[mx]].F);
          gcvt(ta[mx],8,name);
          strcat(name,".tmp");
          F[ta[mx]].F=fopen(name,"w+b");
          F[ta[mx]].eor=0;
          ta[mx]=ta[k2];
          ta[k2]=ta[k1];
          k1--;
          k2--;
        } else
        if (F[ta[mx]].eor)
        {
          // closing series
          tx=ta[mx];
          ta[mx]=ta[k2];
          ta[k2]=tx;
          k2--;
        }
      } while(k2>=0);
      if(j<N-1) j++; else j=Nh;
    } while(k1>=0);
    for(i=0;i<Nh;i++)
    {
      tx=t[i];
      t[i]=t[i+Nh];
      t[i+Nh]=tx;
    }
  } while (l!=1);

  // writing sorted sequence
  rewind(F[0].F);
  fread(&x,sizeof(int),1,F[0].F);
  while (!feof(F[0].F))
  {
    fprintf(output,"%d ",x);
    fread(&x,sizeof(int),1,F[0].F);
  }

  // closing all opened files
  for (i=0;i<N;i++) fclose(F[i].F);
  fclose(input);
  fclose(output);
}



Polyphase merge

Код

//////////////////////////////////////////////////////////////////////////////
//
//  File sort (polyphase merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use N files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into N-1 files, writing first
//      series from C to F1, second one to F2, third - to F3, and so on
//   2) Combine series from files F1,F2,F3,...,F(n-1) to Fn,
//      sorting distributed series
//   3) When we reach the end of one of F1..F(n-1) files we turn sequences
//      and will combine series to this new empty file. For example if we reach
//      end of F3 we will gather data from F1,F2,F4,..Fn to F3
//   4) Repeat first three steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N    6  // number of temporary files (must be greater than 2)

struct ExtFile
{
  FILE *F;
  int first; // current element of this file
  char eor; // indicates end of series
};

  FILE *output;
  ExtFile input;
  ExtFile F[N];  // array of files
  int level,i,j,k,mx,tx,xmin,x,t[N],ta[N],a[N],d[N],z,tn,dn;
  char name[13];

// this functions sets new value of variable j
// on the next step of data distribution we'll write to sequence #j
void select(void)
{
  if (d[j]<d[j+1]) j++;  // d[j] shows number of series in sequence #j
  else
  {
    if (d[j]==0)
    {
      level++;
      z=a[0];
      for (int i=0;i<N-1;i++)
      {
        d[i]=z+a[i+1]-a[i];
        a[i]=z+a[i+1];
      }
    }
    j=0;
  }
  d[j]--;
}

// this function copies data element from x to y, updating (.first) members
void copy(ExtFile *x, ExtFile *y)
{
  y->first=x->first;
  fwrite(&y->first,sizeof(int),1,y->F);
  fread(&x->first,sizeof(int),1,x->F);
  x->eor=(x->first<y->first || feof(x->F));
}

// this function copies series from input to f[j]
void copyrun(void)
{
  do
  {
    F[j].first=input.first;
    fwrite(&F[j].first,sizeof(int),1,F[j].F);
    fscanf(input.F,"%d",&input.first);
    input.eor=input.first<F[j].first;
  } while (!input.eor && !feof(input.F));
  if (feof(input.F))
  {
    if (input.first<F[j].first) select();
    F[j].first=input.first;
    fwrite(&F[j].first,sizeof(int),1,F[j].F);
    d[j]++;
  }
}

void main(void)
{
  // opening required files (file 1.dat must exist)
  input.F=fopen("1.dat","rb");
  fscanf(input.F,"%d ",&input.first);
  F[t[N-1]].eor=0;
  output=fopen("1.srt","wb");
  for (int i=0;i<N-1;i++)
  {
    gcvt(i,8,name);
    strcat(name,".tmp");
    F[i].F=fopen(name,"w+b");
    fread(&F[i].first,sizeof(int),1,F[i].F);
    F[i].eor=0;
    a[i]=1;
    d[i]=1;
  }

  // initializing variables
  level=1;
  j=0;
  a[N-1]=0;
  d[N-1]=0;

  // distributing data from input to first N-1 sequences
  do
  {
    select();
    copyrun();
  } while (!feof(input.F) && j!=N-2);

  while (!feof(input.F))
  {
    select();
    if (F[j].first<=input.first)
    {
      copyrun();
      if (feof(input.F)) d[j]++; else copyrun();
    } else copyrun();
  }

  // preparing first N-1 series for reading
  for (i=0;i<N-1;i++)
  {
    t[i]=i;
    rewind(F[i].F);
    fread(&F[i].first,sizeof(int),1,F[i].F);
    F[i].eor=0;
  }
  t[N-1]=N-1;

  // main loop
  do
  {
    // gathering data from t[0]..t[N-2] into t[N-1]
    z=a[N-2];
    d[N-1]=0;
    // preparing file to write
    fclose(F[t[N-1]].F);
    gcvt(t[N-1],8,name);
    strcat(name,".tmp");
    F[t[N-1]].F=fopen(name,"w+b");
    F[t[N-1]].eor=0;
    do
    {
      // gathering one series
      k=-1;
      for (i=0;i<N-1;i++)
      {
        if (d[i]>0) d[i]--;
        else
        {
          k++;
          ta[k]=t[i];
        }
      }
      if (k==-1) d[N-1]++;
      else
      {
        // gathering one real series from t[0]..t[k] into t[N-1]
        do
        {
          i=0;
          mx=0;
          xmin=F[ta[i]].first;
          // selecting series with minimal element to place it first
          while (i<k)
          {
            i++;
            x=F[ta[i]].first;
            if (x<xmin)
            {
              xmin=x;
              mx=i;
            }
          }
          // copying smallest element to output series
          copy(&F[ta[mx]],&F[t[N-1]]);
          // if we reach the end of the current input sequence
          // or end of series in it then close this source
          if (F[ta[mx]].eor)
          {
            // closing this source
            ta[mx]=ta[k];
            k--;
          }
        } while (k!=-1);
      }  
      z--;
    } while (z!=0);

    // swapping sequences
    rewind(F[t[N-1]].F);
    fread(&F[t[N-1]].first,sizeof(int),1,F[t[N-1]].F);
    F[t[N-1]].eor=0;

    tn=t[N-1];
    dn=d[N-1];
    z=a[N-2];
    for(i=N-1;i>0;i--)
    {
      t[i]=t[i-1];
      d[i]=d[i-1];
      a[i]=a[i-1]-z;
    }
    t[0]=tn;
    d[0]=dn;
    a[0]=z;

    // preparing file F[t[N-1]] to write
    fclose(F[t[N-1]].F);
    gcvt(t[N-1],8,name);
    strcat(name,".tmp");
    F[t[N-1]].F=fopen(name,"w+b");
    F[t[N-1]].eor=0;

    level--;
  } while (level!=0); // while there are more than one series

  // writing sorted sequence from F[t[0]]
  rewind(F[t[0]].F);
  fread(&x,sizeof(int),1,F[t[0]].F);
  while (!feof(F[t[0]].F))
  {
    fprintf(output,"%d ",x);
    fread(&x,sizeof(int),1,F[t[0]].F);
  }

  // closing all opened files
  for (i=0;i<N;i++) fclose(F[i].F);
  fclose(input.F);
  fclose(output);
}
Сайт: forum.vingrad.ru






Просмотров: 2445

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную