A difficult Problem.

This is a discussion on A difficult Problem. within the C Programming forums, part of the General Programming Boards category; Now i am try to implement an External Sort. I assume the computer only have 30 spaces to hold for ...

  1. #1
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24

    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??
    TO RUN FOR FAILURE

  2. #2
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Talking

    What code do you have for it? We will help, but show us what you have so far.
    Mr. C: Author and Instructor

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  4. #4
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24
    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
    TO RUN FOR FAILURE

  5. #5
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24
    ( PUSH UP )
    No one know ? ? ?
    TO RUN FOR FAILURE

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 05:24 PM
  4. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  5. Difficult programming problem
    By ccmac in forum C++ Programming
    Replies: 3
    Last Post: 02-25-2002, 03:58 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21