# A difficult Problem.

• 11-10-2002
Kam
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??
• 11-10-2002
Mister C
What code do you have for it? We will help, but show us what you have so far.
• 11-11-2002
master5001
Assuming there is no limit to the size of the files I would have a small header in each file that describes the data it contains. This sounds a bit like a data base problem (it would be refreshing to see a problem that is unrelated to a homework assignment). But I would need to see a bit of code to see where you are having problems.
• 11-12-2002
Kam
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;   } }```