Thread: A difficult Problem.

Now i am try to implement an External Sort.
I assume the computer only have 30 spaces to hold for the numbers. And now i am going to sort a 10000 numbers in a text file.
We take an array in 30 space, A[30] to represent the memory.
I can sort the file by creating 4 text file.
tape1.txt
tape2.txt
tape3.txt
tape4.txt
and sort the numbers.

but later i found out that we can use only 3 files to sort it and even more quickly....
Can anyone do it??

What code do you have for it? We will help, but show us what you have so far.

Sorry to post it so late.....
Coz i am still working on the improvement of my program.
Here is my program's main code. @.@

Code:

#include <stdio.h>
#include <stdlib.h>
#include "sort5.h"
#include "fatal.h"

void InsertionSort( ElementType A[ ], int N )
        {
            int j, P;
            ElementType Tmp;

/* 1*/      for( P = 1; P < N; P++ )
            {
/* 2*/          Tmp = A[ P ];
/* 3*/          for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )
/* 4*/              A[ j ] = A[ j - 1 ];
/* 5*/          A[ j ] = Tmp;
            }
        }

void PrintFile(FILE *fp, int s)
{
  int i=0, c;
  while (fscanf(fp, "%d", &c)!=EOF)
    {
      printf("%d", c);
      if (++i==s)
        {
          printf("\n");
          i=0;
        }
      else printf(" ");
    }
}

void InitialiseTwoFiles(int N, FILE *fin, FILE *fp1, FILE *fp2) 
{
  ElementType *A;
  int i=0,j,c, turn=1;

  A=malloc(N*sizeof(int));
  while (fscanf(fin, "%d", &c)!=EOF)
    {
      A[i++]=c;
      if (i==N)
        {
          /* read N numbers, sort them next */
          InsertionSort( A, N );
          for (i=0; i<N; i++)
           { 
             if (turn==1)
               fprintf(fp1,"%d ",A[i]);
             else fprintf(fp2,"%d ",A[i]);
           }
          if (turn==1)
            turn=2;
          else turn=1;
          i=0;
        }
    }
  if (i>0)
   {
     InsertionSort( A, i );
     for (j=0; j<i; j++)
       if (turn==1)
         fprintf(fp1,"%d ",A[j]);
       else fprintf(fp2,"%d ",A[j]);
   }
}

int MergeFiles(int CurRunSize,FILE *fpin1, FILE *fpin2, FILE *fpo1, FILE *fpo2)
{
  int md=1,i,eof1,eof2,c1,c2,i1=0,i2=0;

  printf("start MergeFiles ...");

  eof1=fscanf(fpin1, "%d", &c1);
  eof2=fscanf(fpin2, "%d", &c2);   
  if (eof1==EOF || eof2==EOF)
    {
      printf("end MergeFiles, return 0: One file is empty\n");
      return 0;
    }
  while (eof1!=EOF || eof2!=EOF)
    {
      if ( (eof1!=EOF && eof2!=EOF && i1<CurRunSize && i2<CurRunSize && c1<=c2)
          || (eof1!=EOF && (eof2==EOF || i2==CurRunSize) && i1<CurRunSize) )
        {
          if (md==1) 
            fprintf(fpo1,"%d ",c1);
          else fprintf(fpo2,"%d ",c1); 
          printf("%d ",c1);  
          eof1=fscanf(fpin1, "%d", &c1);
          i1++;
        }
      if ( (eof1!=EOF && eof2!=EOF && i1<CurRunSize && i2<CurRunSize && c1>c2)
          || (eof2!=EOF && (eof1==EOF || i1==CurRunSize) && i2<CurRunSize) )
        {  
          if (md==1)
            fprintf(fpo1,"%d ",c2);
          else fprintf(fpo2,"%d ",c2);  
          printf("%d ",c2);
          eof2=fscanf(fpin2, "%d", &c2); 
          i2++;
        }
      if (i1==CurRunSize && i2==CurRunSize)
        {
          if (md==1) md=2; else md=1;
          i1=0;
          i2=0;
        }
    }
  printf("end MergeFiles, return 1\n");
  return 1;
}

void OpenFiles(FILE **pfp1, FILE **pfp2, FILE **pfp3, FILE **pfp4, char *fname1, char *fname2,char *fname3,char *fname4)
{
  if ((*pfp1=fopen(fname1, "r"))==NULL)
    FatalError("cannot open file fname1 for reading");
  if ((*pfp2=fopen(fname2, "r"))==NULL)
    FatalError("cannot open file fname2 for reading");
  if ((*pfp3=fopen(fname3, "w"))==NULL)
    FatalError("cannot open file fname3 for writing");
  if ((*pfp4=fopen(fname4, "w"))==NULL)
    FatalError("cannot open file fname4 for writing");
}

void ExternalSort(int N, FILE *fin)
{ 
  FILE *fp1, *fp2, *fp3, *fp4; 
  int i=0,j,CurRunSize,c,d=1;
                        /* d=0, merge finish; d=1, merge from f1, f2 */
                        /* to f3,f4; d=2, merge from f3,f4 to f1,f2. */
  if ((fp1=fopen("f1", "w"))==NULL)
    FatalError("cannot open file f1 for writing");
  if ((fp2=fopen("f2", "w"))==NULL)
    FatalError("cannot open file f2 for writing");
  InitialiseTwoFiles(N, fin, fp1, fp2);
  fclose(fp1);
  fclose(fp2);
  CurRunSize=N;
  while (d!=0) 
  {
    if (d==1)
      {
        OpenFiles(&fp1,&fp2,&fp3,&fp4,"f1","f2","f3","f4");
      printf("call MergeFiles CurRunSize=%d, d=%d(should d=1)\n", CurRunSize,d);
        if (MergeFiles(CurRunSize,fp1,fp2,fp3,fp4)==0) 
          d=0;
        else d=2;
       }
     else                                      /* d=2 */
      {
        OpenFiles(&fp3,&fp4,&fp1,&fp2,"f3","f4","f1","f2");      
printf("call MergeFiles CurRunSize=%d, d=%d(should d=2)\n", CurRunSize,d);
        if (MergeFiles(CurRunSize,fp3,fp4,fp1,fp2)==0) 
          d=0;
        else d=1;
      }
  fclose(fp1); fclose(fp2); fclose(fp3); fclose(fp4);
  CurRunSize*=2;
  }
}

Code tags added by Hammer

( PUSH UP )
No one know ? ? ?