Quick Sort Program

Question

jazzz 0 Newbie Poster

17 Years Ago

Hi,

The below is a program which uses quick sort to sort numbers in 3 columns LayerCode, SubCode and BrandCode. It sorts first by LayerCode, then by SubCode and then by BrandCode.

The program seems has no errors. but it is not working(i.e., not sorting the numbers). Can anyone have a look and tell me which part has a problem???

/****************************************************************************************
    Sample
****************************************************************************************/

#include "stdafx.h"

FILE    *fp_dump;

/*----- Layer -----*/
/*layer Record*/
typedef struct {
    USHORT          usLayerCode;             /*LayerCode*/
    USHORT          usSubCode;              /*SubCode*/
    USHORT          usBrandCode;                /*BrandCode*/
    USHORT          usStartY;               /*Latitude*/
    USHORT          usStartX;               /*Longitude*/
    UINT            uiAR_DA;                 /*Offset*/
    USHORT          usCellSize;             /*Cell Size*/
    USHORT          usDS;                   /*Relative offset*/
    USHORT        usKey;                /*SortKey*/
} stLayerRec_t;

/*Layer*/
typedef struct {
    USHORT          usRecCnt;           /*Number of IDataRecord*/
    stLayerRec_t     *pstRec;                  /*Layer Record*/
} stLayer_t;


static int iGetLayerFile( char*, stLayer_t* );
static int iLayerCodeSort(const void *, const void * );
static int iSubCodeSort(const void *, const void * );
static int iBrandCodeSort(const void *, const void * );
static int iWriteLayerFile( char *, stLayer_t * );

/******* Sample main function ********/
int main( int argc, char **argv ) {

    int     i,j,k,l,m,sMax,dMax;
    int    cnt;

      FINDFILES_T stFinds;
      FINDFILES_T stFindsFiles;
      stLayer_t stILF;

    DIR* dir;
        
    char   acFileName[128],cmd[128];
    char   *temp, *pch;

    char   acILFDir[128];                
    char   acNewILFDir[128];
      char   dirPath[128];         

    if (argv[1] == NULL || argv[2] == NULL)
    {
        printf("\n<Usage>\nLayerFileSort source dest\n\n");
        exit( NG );
    } 

    sMax = strlen(argv[1]);
      dMax = strlen(argv[2]);
    memcpy(acILFDir, argv[1],sMax+2);
     memmove(acILFDir+sMax,"/\0",2);
    memcpy(acNewILFDir, argv[2],dMax+2);
      memmove(acNewILFDir+dMax,"/\0",2);
 
    if ((fp_dump=fopen("LayerFile.txt", "w")) == NULL) {
                printf( "LogFile Open error\n" );
                exit( NG );
    }

      memset(&stFinds, 0, sizeof(FINDFILES_T));

    /*Search ILF directories*/
        if ((FindFiles(acILFDir, &stFinds)) == NG) {
                exit( NG );
        }
        for (i=0 ; i<stFinds.iFileCnt ; i++) {
        memset(&stFindsFiles, 0, sizeof(FINDFILES_T));
        
        /*Search ILF files*/
        if ((FindFiles(stFinds.pcPathName[i], &stFindsFiles)) == NG) {
                exit( NG );
        }
        for (j=0 ; j<stFindsFiles.iFileCnt ; j++) {
    
            printf("%5d: %s\n", i, stFindsFiles.pcPathName[j] );
            
            /*get ILF*/
            if( iGetLayerFile( stFindsFiles.pcPathName[j], &stILF ) != OK ){
                printf("ILF reading error : %s\n",stFindsFiles.pcPathName[j] );
                exit( NG );
            }

            /*sort ILF*/

            qsort(stILF.pstRec,stILF.usRecCnt,sizeof(stLayerRec_t),iLayerCodeSort);
            qsort(stILF.pstRec,stILF.usRecCnt,sizeof(stLayerRec_t),iSubCodeSort);
            qsort(stILF.pstRec,stILF.usRecCnt,sizeof(stLayerRec_t),iBrandCodeSort);

            /*get filename*/
            memcpy( acFileName, acNewILFDir,strlen(acNewILFDir));

            for ( m = (int)strlen ( acNewILFDir ),l = (int)strlen ( acILFDir ); 
                l < (int)strlen( stFindsFiles.pcPathName[j] ); l++, m++ )
                acFileName[m] = stFindsFiles.pcPathName[j][l];

            acFileName[m] = '\0';
        
            temp = (char *)malloc(strlen(acFileName)+1);
            if ( NULL == temp )
            {
                printf ("temp malloc error!");
                exit (NG);
            }

            memcpy(temp,acFileName,strlen(acFileName)+1); 
            pch = (char *)malloc(strlen(acFileName)+1);
            if ( NULL == pch )
              {
                printf("pch malloc error!");
                exit (NG);
            }
            memcpy(pch,acFileName,strlen(acFileName)+1);
            pch = strrchr(temp,'/');
            cnt = pch - temp + 1;

            memcpy(dirPath,temp,cnt);
            
            dirPath[cnt] = '\0';

              dir = opendir(dirPath);
            if (!dir) 
            {
                  sprintf(cmd,"mkdir -m 755 -p %s",dirPath);  
                  printf("Making directory :%s\n",dirPath);  
                /*      printf("cmd:%s\n",cmd);  */
                  system (cmd);           
            } 
            
            else closedir(dir); 
         
            /*write ILF(finshed sortting)*/                              
            if( iWriteLayerFile ( acFileName, &stILF ) != OK ){
                printf("ILF writing error : %s\n",acFileName );
                exit( NG );
            }
        
            /*        dump list */
            for ( k = 0; k < stILF.usRecCnt; k++ ){
fprintf(fp_dump, "%s,%d,%d,%d,0x%04x,0x%04x,0x%04x,0x%02x,0x%02x,%d\n",
                stFindsFiles.pcPathName[j],
                stILF.pstRec[k].usLayerCode,
                stILF.pstRec[k].usSubCode,
                stILF.pstRec[k].usBrandCode,
                stILF.pstRec[k].usStartX,
                stILF.pstRec[k].usStartY,
                stILF.pstRec[k].uiAR_DA,
                stILF.pstRec[k].usCellSize,
                stILF.pstRec[k].usDS,
                stILF.pstRec[k].usKey);
            }     

            if(stILF.usRecCnt != 0) free (stILF.pstRec);        
        }
        FindFree(&stFindsFiles);
    }
        FindFree(&stFinds);        
    fclose(fp_dump);
 
    free(temp);
    free(pch);
    printf("Done!\n");
     exit( OK );
}
/*======================================================================
     FUNCTION     : Get LayerFile
     INPUT        : char*            -FileName
            stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iGetLayerFile( char *acFileName, stLayer_t *pstILF)
{
    FILE    *fp;
    int      i,j;
    USHORT    usSortKey[SORT_REC] = {9126,7328,7373,7315,7387,7314,7313,7369,9999,7395,7311,7321};
    
    pstILF->usRecCnt = 0;

    if ((fp=fopen(acFileName, "rb")) == NULL) {
        return ( NG );
    }
    fread(&pstILF->usRecCnt, 2, 1, fp);  /* Number of Layer */

        if( pstILF->usRecCnt != 0 ){
            pstILF->pstRec =
                (stLayerRec_t*)calloc(pstILF->usRecCnt,sizeof(stLayerRec_t) );
    }

    for( i = 0; i < (int)pstILF->usRecCnt; i++ ){
        fread(&pstILF->pstRec[i].usLayerCode, 2, 1, fp);        /* Layer Code*/
        fread(&pstILF->pstRec[i].usSubCode, 2, 1, fp);            /* Sub Code*/
        fread(&pstILF->pstRec[i].usBrandCode, 2, 1, fp);        /* Brand Code*/

        fread(&pstILF->pstRec[i].usStartY, 2, 1, fp);            /* Lat*/
        fread(&pstILF->pstRec[i].usStartX, 2, 1, fp);            /* Long*/
        fread(&pstILF->pstRec[i].uiAR_DA, 4, 1, fp);            /* Offset*/
        fread(&pstILF->pstRec[i].usCellSize, 2, 1, fp);            /* CellSize*/
        fread(&pstILF->pstRec[i].usDS, 2, 1, fp);            /* RelativeOffset*/

        pstILF->pstRec[i].usKey = 0;                        /* Sort Key */
        for ( j = 0; j < SORT_REC; j++ ){
            if( pstILF->pstRec[i].usLayerCode == usSortKey[j] ){
                pstILF->pstRec[i].usKey = j + 1;                /* Sort Key*/
                break;
            }
        }
    }
  
    fclose( fp );

    return( OK );
}
/*======================================================================
     FUNCTION     : WriteLayerFile
     INPUT        : char*            -FileName
                    stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iWriteLayerFile( char *acFileName, stLayer_t *pstILF)
{
    FILE    *fp;
    int    i;
    
    if ((fp=fopen(acFileName, "wb")) == NULL) {
        return ( NG );
    }
    fwrite(&pstILF->usRecCnt, 2, 1, fp);  /* Number of Layer */
    
    for( i = 0; i < (int)pstILF->usRecCnt; i++ ){
        fwrite(&pstILF->pstRec[i].usLayerCode, 2, 1, fp);        /* Layer Code*/
        fwrite(&pstILF->pstRec[i].usSubCode, 2, 1, fp);        /* Sub Code*/
        fwrite(&pstILF->pstRec[i].usBrandCode, 2, 1, fp);        /* Brand Code*/
        fwrite(&pstILF->pstRec[i].usStartY, 2, 1, fp);            /* Lat*/
        fwrite(&pstILF->pstRec[i].usStartX, 2, 1, fp);            /* Long*/
        fwrite(&pstILF->pstRec[i].uiAR_DA, 4, 1, fp);            /* Offset*/
        fwrite(&pstILF->pstRec[i].usCellSize, 2, 1, fp);            /* CellSize*/
        fwrite(&pstILF->pstRec[i].usDS, 2, 1, fp);            /* RelativeOffset*/
        
    };
    fclose( fp );

    return( OK );
}
/*======================================================================
     FUNCTION     : iLayerCodeSort
     INPUT        : stLayer_t    -Layer
            stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/

static int iLayerCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;

    iDiff = (int)pstLayer1->usKey - (int)pstLayer2->usKey;

    return( iDiff );
}

/*======================================================================
     FUNCTION     : iSubCodeSort
     INPUT        : stLayer_t    -Layer
                    stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iSubCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;

    
          iDiff = (int)pstLayer1->usSubCode - (int)pstLayer2->usSubCode;

       return( iDiff );
}

/*======================================================================
     FUNCTION     : iBrandCodeSort
     INPUT        : stLayer_t    -Layer
                    stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iBrandCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;

    
          iDiff = (int)pstLayer1->usBrandCode - (int)pstLayer2->usBrandCode;

       return( iDiff );
}

Thankx
Jazz

c

2 Contributors
2 Replies
111 Views
6 Hours Discussion Span
Latest Post 17 Years Ago Latest Post by jazzz

All 2 Replies

Salem 5,138 Posting Sage

17 Years Ago

C'mon, you could have at least posted your most recent attempt at the code
http://forums.devshed.com/c-programming-42/sorting-356010.html

This post here is nearly an hour newer than your reply to my original comments, yet it's the old code.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

jazzz 0 Newbie Poster · Answer 1 · 2006-05-30T20:34:02+00:00

Oh, That was a mistake. The recent code is as follows, but still not working. Any help would be appriciated.

****************************************/

#include "stdafx.h"

FILE    *fp_dump;

/*----- Layer -----*/
/*layer Record*/
typedef struct {
    USHORT          usLayerCode;             /*LayerCode*/
    USHORT          usSubCode;              /*SubCode*/
    USHORT          usBrandCode;                /*BrandCode*/
    USHORT          usStartY;               /*Latitude*/
    USHORT          usStartX;               /*Longitude*/
    UINT            uiAR_DA;                 /*Offset*/
    USHORT          usCellSize;             /*Cell Size*/
    USHORT          usDS;                   /*Relative offset*/
    USHORT        usKey;                /*SortKey*/
} stLayerRec_t;

/*Layer*/
typedef struct {
    USHORT          usRecCnt;           /*Number of IDataRecord*/
    stLayerRec_t     *pstRec;                  /*Layer Record*/
} stLayer_t;


static int iGetLayerFile( char*, stLayer_t* );
static int iLayerCodeSort(const void *, const void * );
static int iSubCodeSort(const void *, const void * );
static int iBrandCodeSort(const void *, const void * );
static int iWriteLayerFile( char *, stLayer_t * );
static int iCompare(const void *, const void * );


/******* Sample main function ********/
int main( int argc, char **argv ) {

    int     i,j,k,l,m,sMax,dMax;
    int    cnt;

      FINDFILES_T stFinds;
      FINDFILES_T stFindsFiles;
      stLayer_t stILF;

    DIR* dir;
        
    char   acFileName[128],cmd[128];
    char   *temp, *pch;

    char   acILFDir[128];                
    char   acNewILFDir[128];
      char   dirPath[128];         

    if (argv[1] == NULL || argv[2] == NULL)
    {
        printf("\n<Usage>\nLayerFileSort source dest\n\n");
        exit( NG );
    } 

    sMax = strlen(argv[1]);
      dMax = strlen(argv[2]);
    memcpy(acILFDir, argv[1],sMax+2);
     memmove(acILFDir+sMax,"/\0",2);
    memcpy(acNewILFDir, argv[2],dMax+2);
      memmove(acNewILFDir+dMax,"/\0",2);
 
    if ((fp_dump=fopen("LayerFile.txt", "w")) == NULL) {
                printf( "LogFile Open error\n" );
                exit( NG );
    }

      memset(&stFinds, 0, sizeof(FINDFILES_T));

    /*Search ILF directories*/
        if ((FindFiles(acILFDir, &stFinds)) == NG) {
                exit( NG );
        }
        for (i=0 ; i<stFinds.iFileCnt ; i++) {
        memset(&stFindsFiles, 0, sizeof(FINDFILES_T));
        
        /*Search ILF files*/
        if ((FindFiles(stFinds.pcPathName[i], &stFindsFiles)) == NG) {
                exit( NG );
        }
        for (j=0 ; j<stFindsFiles.iFileCnt ; j++) {
    
            printf("%5d: %s\n", i, stFindsFiles.pcPathName[j] );
            
            /*get ILF*/
            if( iGetLayerFile( stFindsFiles.pcPathName[j], &stILF ) != OK ){
                printf("ILF reading error : %s\n",stFindsFiles.pcPathName[j] );
                exit( NG );
            }

            /*sort ILF*/

            qsort(stILF.pstRec,stILF.usRecCnt,sizeof(stLayerRec_t),iCompare);
            
            /*get filename*/
            memcpy( acFileName, acNewILFDir,strlen(acNewILFDir));

            for ( m = (int)strlen ( acNewILFDir ),l = (int)strlen ( acILFDir ); 
                l < (int)strlen( stFindsFiles.pcPathName[j] ); l++, m++ )
                acFileName[m] = stFindsFiles.pcPathName[j][l];

            acFileName[m] = '\0';
        
            temp = (char *)malloc(strlen(acFileName)+1);
            if ( NULL == temp )
            {
                printf ("temp malloc error!");
                exit (NG);
            }

            memcpy(temp,acFileName,strlen(acFileName)+1); 
            pch = (char *)malloc(strlen(acFileName)+1);
            if ( NULL == pch )
              {
                printf("pch malloc error!");
                exit (NG);
            }
            memcpy(pch,acFileName,strlen(acFileName)+1);
            pch = strrchr(temp,'/');
            cnt = pch - temp + 1;

            memcpy(dirPath,temp,cnt);
            
            dirPath[cnt] = '\0';

              dir = opendir(dirPath);
            if (!dir) 
            {
                  sprintf(cmd,"mkdir -m 755 -p %s",dirPath);  
                  printf("Making directory :%s\n",dirPath);  
                /*      printf("cmd:%s\n",cmd);  */
                  system (cmd);           
            } 
            
            else closedir(dir); 
         
            /*write ILF(finshed sortting)*/                              
            if( iWriteLayerFile ( acFileName, &stILF ) != OK ){
                printf("ILF writing error : %s\n",acFileName );
                exit( NG );
            }
        
            /*        dump list */
            for ( k = 0; k < stILF.usRecCnt; k++ ){
fprintf(fp_dump, "%s,%d,%d,%d,0x%04x,0x%04x,0x%04x,0x%02x,0x%02x,%d\n",
                stFindsFiles.pcPathName[j],
                stILF.pstRec[k].usLayerCode,
                stILF.pstRec[k].usSubCode,
                stILF.pstRec[k].usBrandCode,
                stILF.pstRec[k].usStartX,
                stILF.pstRec[k].usStartY,
                stILF.pstRec[k].uiAR_DA,
                stILF.pstRec[k].usCellSize,
                stILF.pstRec[k].usDS,
                stILF.pstRec[k].usKey);
            }     

            if(stILF.usRecCnt != 0) free (stILF.pstRec);        
        }
        FindFree(&stFindsFiles);
    }
        FindFree(&stFinds);        
    fclose(fp_dump);
 
    free(temp);
    free(pch);
    printf("Done!\n");
     exit( OK );
}
/*======================================================================
     FUNCTION     : Get LayerFile
======================================================================*/
static int iGetLayerFile( char *acFileName, stLayer_t *pstILF)
{
    FILE    *fp;
    int      i,j;
    USHORT    usSortKey[SORT_REC] = {9126,7328,7373,7315,7387,7314,7313,7369,9999,7395,7311,7321};
    
    pstILF->usRecCnt = 0;

    if ((fp=fopen(acFileName, "rb")) == NULL) {
        return ( NG );
    }
    fread(&pstILF->usRecCnt, 2, 1, fp);  /* Number of Layer */

        if( pstILF->usRecCnt != 0 ){
            pstILF->pstRec =
                (stLayerRec_t*)calloc(pstILF->usRecCnt,sizeof(stLayerRec_t) );
    }

    for( i = 0; i < (int)pstILF->usRecCnt; i++ ){
        fread(&pstILF->pstRec[i].usLayerCode, 2, 1, fp);        /* Layer Code*/
        fread(&pstILF->pstRec[i].usSubCode, 2, 1, fp);            /* Sub Code*/
        fread(&pstILF->pstRec[i].usBrandCode, 2, 1, fp);        /* Brand Code*/

        fread(&pstILF->pstRec[i].usStartY, 2, 1, fp);            /* Lat*/
        fread(&pstILF->pstRec[i].usStartX, 2, 1, fp);            /* Long*/
        fread(&pstILF->pstRec[i].uiAR_DA, 4, 1, fp);            /* Offset*/
        fread(&pstILF->pstRec[i].usCellSize, 2, 1, fp);            /* CellSize*/
        fread(&pstILF->pstRec[i].usDS, 2, 1, fp);            /* RelativeOffset*/

        pstILF->pstRec[i].usKey = 0;                        /* Sort Key */
        for ( j = 0; j < SORT_REC; j++ ){
            if( pstILF->pstRec[i].usLayerCode == usSortKey[j] ){
                pstILF->pstRec[i].usKey = j + 1;                /* Sort Key*/
                break;
            }
        }
    }
  
    fclose( fp );

    return( OK );
}
/*======================================================================
     FUNCTION     : WriteLayerFile
==============================================*/
static int iWriteLayerFile( char *acFileName, stLayer_t *pstILF)
{
    FILE    *fp;
    int    i;
    
    if ((fp=fopen(acFileName, "wb")) == NULL) {
        return ( NG );
    }
    fwrite(&pstILF->usRecCnt, 2, 1, fp);  /* Number of Layer */
    
    for( i = 0; i < (int)pstILF->usRecCnt; i++ ){
        fwrite(&pstILF->pstRec[i].usLayerCode, 2, 1, fp);        /* Layer Code*/
        fwrite(&pstILF->pstRec[i].usSubCode, 2, 1, fp);        /* Sub Code*/
        fwrite(&pstILF->pstRec[i].usBrandCode, 2, 1, fp);        /* Brand Code*/
        fwrite(&pstILF->pstRec[i].usStartY, 2, 1, fp);            /* Lat*/
        fwrite(&pstILF->pstRec[i].usStartX, 2, 1, fp);            /* Long*/
        fwrite(&pstILF->pstRec[i].uiAR_DA, 4, 1, fp);            /* Offset*/
        fwrite(&pstILF->pstRec[i].usCellSize, 2, 1, fp);            /* CellSize*/
        fwrite(&pstILF->pstRec[i].usDS, 2, 1, fp);            /* RelativeOffset*/
        
    };
    fclose( fp );

    return( OK );
}
/*======================================================================
     FUNCTION     : iLayerCodeSort
     INPUT        : stLayer_t    -Layer
            stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/

static int iLayerCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;

    if(pstLayer1->usLayerCode < pstLayer2->usLayerCode)
          iDiff = -1;
    else if(pstLayer1->usLayerCode > pstLayer2->usLayerCode)
          iDiff = 1;
    else 
 iDiff = 0;

return( iDiff );
}

/*======================================================================
     FUNCTION     : iSubCodeSort
     INPUT        : stLayer_t    -Layer
                    stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iSubCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;

        if(pstLayer1->usSubCode < pstLayer2->usSubCode)
          iDiff = -1;
    else if(pstLayer1->usSubCode > pstLayer2->usSubCode)
          iDiff = 1;
    else 
 iDiff = 0;

return( iDiff );

}

/*======================================================================
     FUNCTION     : iBrandCodeSort
     INPUT        : stLayer_t    -Layer
                    stLayer_t    -Layer
     RETURN       : OK / NG
======================================================================*/
static int iBrandCodeSort(const void *data1, const void *data2 )
{
    stLayerRec_t     *pstLayer1;
    stLayerRec_t     *pstLayer2;
    int             iDiff;

    pstLayer1 = (stLayerRec_t*)data1;
    pstLayer2 = (stLayerRec_t*)data2;
    
    if(pstLayer1->usBrandCode < pstLayer2->usBrandCode)
          iDiff = -1;
    else if(pstLayer1->usBrandCode > pstLayer2->usBrandCode)
          iDiff = 1;
    else 
 iDiff = 0;

return( iDiff );
}

static int iCompare(const void *data1, const void *data2 )
{
  int result;
  result = iLayerCodeSort(data1, data2);
  if (result == 0) {  result = iSubCodeSort(data1, data2); }
  if(result == 0) { result = iBrandCodeSort(data1, data2); }
  
  return result;
}

Thankx jazz

Quick Sort Program

Recommended Answers Collapse Answers

All 2 Replies

Recommended Answers