![]() |
|
![]() |
|
|
Thread Tools | Display Modes |
|
|
|
|
#1 |
|
Newbie
Join Date: May 2006
Posts: 18
Rep Power: 0
![]() |
Quick Sort program
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 has no errors. but it is not working(i.e., not sorting the numbers). Can anyone help me to figure out the 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 |
|
|
|
|
|
#2 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 824
Rep Power: 4
![]() |
Calling qsort 3 times will end up sorting the array 3 times. The final sort will take precedence, so the items will end up in branding order - is this what is happening?
You only need to call qsort once, just change your sort callback function to check LayerCode, SubCode and then BrandCode. i.e. if the LayerCode is the same, then check SubCode, if the SubCode is the same, check BrandCode. Also note that your LayerCode sort was using the usKey field, not the usLayer field. static int iSortEverything(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->usLayerCode - (int)pstLayer2->usLayerCode;
if (iDiff != 0)
return iDiff;
iDiff = (int)pstLayer1->usSubCode - (int)pstLayer2->usSubCode;
if (iDiff != 0)
return iDiff;
iDiff = (int)pstLayer1->usBrandCode - (int)pstLayer2->usBrandCode;
return( iDiff );
} |
|
|
|
|
|
#3 |
|
Newbie
Join Date: May 2006
Posts: 18
Rep Power: 0
![]() |
Hi,
Thanks for the reply. I made the changes u sggested. But its still not working. Can u please guide me. /****************************************************************************************
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 iWriteLayerFile( char *, stLayer_t * );
static int iSort(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),iSort);
/*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 : iSort
INPUT : stLayer_t -Layer
stLayer_t -Layer
RETURN : OK / NG
======================================================================*/
static int iSort(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->usLayerCode - (int)pstLayer2->usLayerCode;
if iDiff != 0) return iDiff;
iDiff = (int)pstLayer1->usSubCode - (int)pstLayer2->usSubCode;
if iDiff != 0) return iDiff;
iDiff = (int)pstLayer1->usBrandCode - (int)pstLayer2->usBrandCode;
if iDiff != 0) return iDiff;
}Thankx jazz |
|
|
|
|
|
#4 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 824
Rep Power: 4
![]() |
Can you attach a sample input file so I can try it out?
|
|
|
|
|
|
#5 |
|
Newbie
Join Date: May 2006
Posts: 18
Rep Power: 0
![]() |
Hi,
Please find attached the sample input file. In the file, second field is the Layer Code, third is Sub Code and fourth field is Brand Code. Thankx jazz |
|
|
|
|
|
#6 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 824
Rep Power: 4
![]() |
That looks more like an output file rather than an input file.
The program seems to be looking at all the files in a directory, but it is only sorting the records of each file as it reads them, and then dumping them out to the same output file (LayerFile.txt). This will result in LayerFile.txt having blocks of sorted output, but nothing has sorted the whole lot. How many input files are you processing in each run? I would recommend putting a line like: fprintf(fp_dump, "%s:\n", stFindsFiles.pcPathName[j]); |
|
|
|
|
|
#7 | |
|
Newbie
Join Date: May 2006
Posts: 18
Rep Power: 0
![]() |
Hi,
Yes the program looks at all the files in the directory. There is a directory, which has "n" number of directories and each sub-directory has files. For example there is directory X, which has sub directories like 2924 and 3024(like the ones in red); and each subdirectory has files like 0108602924, 0108302924, 0108292924; and this file have the format of Layer code, SubCode, BrandCode and so on(part highlighted in green). The below is the extract of a dump. Quote:
Jazz |
|
|
|
|
![]() |
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|