How to sort random access file?

wmmccoy0910 · #1 27-Aug-2006, 13:22

Hello again folks!
This post is the lastest (and likely last) question I have for this project. Again, I searched the forum and the tutorial but could not find a solution that fits.

What I'm after is a way to perform a sort on a group of random-access records based on a particular field in the file. In this case, last name, ascending.

Here's what I have so far, and for what I can see, it doesn't do anything, right or wrong. And yes, I know the code I'm including doesn't work, but I am including it to give some insight to what kind of track I'm on, even if totally WAY off base.

The code snippets:

CPP / C++ / C Code:

typedef struct customer_s
{
        int acct;
        char firstname[ 25 ];
        char lastname[ 25 ];
        char address[ 30 ];
        char city[ 25 ];
        char state[ 3 ];
        char zip [ 6 ];
        int package[ 5 ];
        double weight[ 5 ];
        char zone[ 5 ][ 2 ];
        double charges[ 5 ];
} customer_t;
/*
.
.
.

void sort_data( FILE *fPtr )
{
 
    int eof_flg;                 /* eof flag                   */
    int acct;		         /* customer acct #            */ 

    char sort1[ 25 ];            /* holds first sort value     */
    char sort2[ 25 ];            /* holds second sort value    */

    customer_t customer1;        /* create structure 1         */
    customer_t customer2;        /* create structure 2         */
    customer_t customer_temp;    /* create temp structure      */

/* other code
.
.
.*/
	while( sorted == 0 )
        {
            /* originally the top of this loop was: did not affect file (didn't work)
            while( fread( &customer1, sizeof( customer_t ), 1, fPtr ) != 0 ) */

            while( 1 )
            {
               eof_flg = fseek( fPtr, ( acct - 1 ) * sizeof( customer_t ), SEEK_SET );
               
               /* this ain't going to work         
               if( eof_flg == 0 )
               {
                   sorted = 1;
                   break;
               }*/
                        
               fread( &customer1 , sizeof( customer_t ), 1, fPtr );
               strcpy( sort1, customer1.lastname );
                        
               // set record position pointer to previous
               eof_flg = fseek( fPtr, -sizeof( customer_t ), SEEK_CUR );
                                                    
               // get next record
                        acct++;
                        
               eof_flg = fseek( fPtr, ( acct - 1 ) * sizeof( customer_t ), SEEK_SET );
                        
                                     
               fread( &customer2, sizeof( customer_t ), 1, fPtr );
               strcpy( sort2, customer2.lastname );
                        
               if( strcmp( sort1, sort2 ) > 0 )
               {
                   //printf( "program says that %s > %s\n", sort1, sort2 );
                   // store data to structures
                            
                   customer_temp = customer1;
                   customer1 = customer2;
                   customer2 = customer_temp;
                            
                   // jump back to first record for this pass and write new data
                   fseek( fPtr, -sizeof( customer_t ) * 2, SEEK_CUR );
                   fwrite( &customer2, sizeof( customer_t ), 1, fPtr );
                            
                   // jump ahead to next record 
                   // this should be the record we were at before "if" statement
                            
                   fseek( fPtr, sizeof( customer_t ) * 2, SEEK_SET ); 
                   fwrite( &customer1, sizeof( customer_t ), 1, fPtr );
                                                    
                 }
                        
                            
            }
                     
       }
}

I apologize for being more of a taker than a giver at this time. I certainly hope as time goes by, I be able to look back on this stuff that I'm having a difficulties with disbelief.

As always, any advice or help would be appreciated, I can see light at the end of the tunnel!

Mike M.

WaltP · #2 27-Aug-2006, 20:59

Personally, I would not want to sort live data in a live file the way you are attempting it. One miscalcuation and your entire file is hosed. What I might do is set up another structure:

CPP / C++ / C Code:

typedef struct 
{
     int offset;
     char firstname[ 25 ];
     char lastname[ 25 ];
}

Read each record loading
1) the starting byte of the record
2) last name
3) first name
into an array of this structure.

Sort this structure.

Create a new file with the sorted order by seeking to the offset position, reading the old file, writing to the new file as you go from the top to bottom of the structure.

I used this on a file sorting program. Using the sort keys as the positions within each line to save I simply copied those positions from each line storing the byte position of the line section. Sorting was very fast, and the rewrite was seamless and quick.

Quote:

I apologize for being more of a taker than a giver at this time.

No need to apologize for that. At the beginning that's pretty much all you can do, but as time goes on, you can give some advice as your skills develop.

wmmccoy0910 · #3 28-Aug-2006, 08:21

Quote:

No need to apologize for that. At the beginning that's pretty much all you can do, but as time goes on, you can give some advice as your skills develop.

Thank you very much for your solution and most of all, your understanding!

Mike M.

#4 28-Aug-2006, 11:59

Quote:

Originally Posted by WaltP

Read each record loading
1) the starting byte of the record
2) last name
3) first name
into an array of this structure.

What size of array do you use for this requirement? Wouldn't a linked-list be a better recommendation? And, instead of sorting the structure, wouldn't you sort the array?

:davis:

WaltP · #5 28-Aug-2006, 13:33

Quote:

Originally Posted by davis

What size of array do you use for this requirement? Wouldn't a linked-list be a better recommendation? And, instead of sorting the structure, wouldn't you sort the array?

A linked list would also work, but I made the assumption the OP was new enough to not know what a linked list was. Therefore I chose an easier way to implement the structure. As for the size, he knows his program and data and can decide on the size himself. If he understands malloc() he can use it, or, because he's a beginner, he can simply use the knowledge of the data at hand during this learning phase and get more compicated as his skills advance. No need to attempt to learn too much too fast and get frustrated.

#6 28-Aug-2006, 17:45

Quote:

Originally Posted by WaltP

A linked list would also work, but I made the assumption the OP was new enough to not know what a linked list was. Therefore I chose an easier way to implement the structure. As for the size, he knows his program and data and can decide on the size himself. If he understands malloc() he can use it, or, because he's a beginner, he can simply use the knowledge of the data at hand during this learning phase and get more complicated as his skills advance. No need to attempt to learn too much too fast and get frustrated.

Okay, but then shouldn't you at least make sure that the advice given is legal C?

Quote:

Originally Posted by WaltP

CPP / C++ / C Code:

typedef struct 
{
     int offset;
     char firstname[ 25 ];
     char lastname[ 25 ];
}

...we tend to use a semi-colon at the end of the declaration so that it doesn't confuse the preprocessor, which otherwise will think that it is a function body. Also, when we use "typedef" we try to include a new type name for the type that we're defining, otherwise, there isn't much value to it. Here is a syntactic improvement.

CPP / C++ / C Code:

typedef struct st_record
{
    int offset;
    char firstname[ 25 ];
    char lastname[ 25 ];
} RECORD;

It seems to me that you're talking about an array of structures. If we are to assume that the array is either defined with a finite size: e.g.

CPP / C++ / C Code:

RECORD records[1000];

...that we won't know if 1000 will hold enough to parse the file or not or if it is too large or what, correct?

Now you said that: As for the size, he knows his program and data and can decide on the size himself.

What happens if the OP was handed a file of some arbitrary length file containing anywhere between a few records to possibly hundreds or even more? Are you advocating that the user count the number of possible records in order to know the data sizing requirements? ...all in order to come up with a finite array size?

I agree that dynamic memory tends to be more complicated, but at what point do you recommend that newcomers start getting their heads around it? It seems to me that the proper point would be when it is warranted by the coding effort, what are your thoughts on this topic?

I think that we're finding some ground where the on-ramp to what seems to be required by the coding project has a certain degree of difficulty associated with it. You tend to advocate "don't learn too much early on because it will confuse you." I tend to advocate "learn what is needed by the requirements." Obviously, we don't have stringent requirements here, but I think that we can reasonably assert that the linked-list approach is probably the easiest and most assured way of solving the problem of reading in records from a file of an unknown number of records and then sorting them before writing them back out to another file.

With regard to dynamic memory allocation, we do not have to realloc if parsing through the file determines that our initial allocation size is inadequate. We don't waste memory by allocating too large of a size at the outset. We do not have to continually check for array boundary limit problems. And, we do not have to perform manual array element management during our sort routine. Of course, we do deal more directly with pointers and those are always an areas of difficulty for newcomers. However, I contend that it is probably a better choice to direct the newcomer to begin using the "right" approach rather than just banging away using inappropriate allocation choices. Additionally, I believe strongly that one's programming life is not just a set of experiences learned throughout the process, but also a base of (potentially) reusable code that quickly allows the user to meet the demanding needs of new projects over the course of a career. In other words, by establishing a useful base of reusable code (such as a generic linked list "library") the programmer builds upon lessons learned and reuses the tools that he has proven time and time again.

I believe that there is no "getting over" with the complexities of C (or C++) in some areas that seem to trouble newbies most...other than to run face into them and be knocked down a few times until one fully understands them. By postponing them, I feel that you stand to further create a dependency on poor coding choices all in the sake of preserving the "wet behind the ears" status for a little while longer.

Granted, typical of newbie posts here, at least 90% seem to have absolutely zero directed thinking skills to the point of not even being able to read the Guidelines post, which is highlighted and practically "demanding" of attention. Perhaps as offerers of advice, we should evaluate the OP on a basis that says, if s/he posted using reasonable attention to the guidelines, then we offer advice that is based on what is appropriate as opposed to what is "simplest and perhaps easier for pure newbies?" I believe that if we adopt the position of providing more targeted advice that does create in the OP a requirement to research the advice content, that we do better for the OP than simply giving a purely newbie "solution" or "guideline" to follow. Also, we may find that, over who knows how much time, that we truly increase the value of coding quality that comes from individuals who have visited these forums.

In other words, I don't want to see you always recommending finite array sizes to every new poster. Finite arrays are very rarely the appropriate response to situations where a number of unknowns are involved. Of course, you're welcomed to differ with my opinion, but the story of not overwhelming the newbies is getting a bit tired. When is it appropriate to show the wizard behind the curtain? Why can't we treat everyone as if they know the fundamentals of the language? Surely it isn't THAT difficult to look them up in any number of places...and if not, what does that say about the educational environments that seem to be sprouting most of these requests for help?

Okay, so if someone says that they are a total newbie, what response do we offer them? Read K&R? That seems like it would be a better signature for you than what you've currently got running...particularly considering how many times you have to remind them to read the guidelines.

In fact, on the topic of K&R, we don't find a lack of discussion involving pointers and arrays. In fact, your suggestion of using an array isn't as simplistic as we can possibly get, is it? We could declare the same number of variables as we would have records in the file, but that would be considered preposterous, wouldn't it!? Why then can't you accept that some find it equally preposterous to use a finitely declared array when a linked list is the "right" storage choice? Obviously you feel that "right" is arguable. How about sharing some of your points as to why you feel that a linked list is more difficult than managing a static array? If we closely look at those difficulties, and if we compare them to "dynamic arrays," don't we find that the basis of the difficulties is in understanding pointers? Why don't we thrust forth with pointers so that newcomers more quickly realize their power, their pitfalls and their usage and utility to conventional C programming? Why hide them in the dark acting as if they are magic and with only the right incantations may they be exploited and that only sorcerers of the greatest skill may hold them in their bag of tricks? Why not dispel the myths and folklore and simply get them out in the open as quickly as possible so that the "fear" of them is more readily removed?

I guess that you have your motivations and that I have mine, but what of them best helps the newbie? Perhaps you are overly comfortable to them and I am overly course? What blend of these is "just right" is obviously contingent upon the individual's skills. I don't see any other means of judging skill except through the quality of posts. My point is that based on the quality of the OP's originating post, I think that we can offer more complexity even if he is profusely declaring a relationship of "taking" versus contributing. Besides, wouldn't it be nice to see "them" come along at a better rate than your constant nagging to read the guidelines' group?

Please excuse the lengthy reply. My aim is to truly increase the potential for quality skills development including all OPs and respondents, including me.

:davis:

#7 29-Aug-2006, 19:23

Quote:

Originally Posted by wmmccoy0910

CPP / C++ / C Code:

typedef struct customer_s
{
        int acct;
        char firstname[ 25 ];
        char lastname[ 25 ];
        char address[ 30 ];
        char city[ 25 ];
        char state[ 3 ];
        char zip [ 6 ];
        int package[ 5 ];
        double weight[ 5 ];
        char zone[ 5 ][ 2 ];
        double charges[ 5 ];
} customer_t;

Do you have a sample of your input file contents?

:davis:

wmmccoy0910 · #8 31-Aug-2006, 16:11

Quote:

Originally Posted by WaltP

A linked list would also work, but I made the assumption the OP was new enough to not know what a linked list was. Therefore I chose an easier way to implement the structure. As for the size, he knows his program and data and can decide on the size himself. If he understands malloc() he can use it, or, because he's a beginner, he can simply use the knowledge of the data at hand during this learning phase and get more compicated as his skills advance. No need to attempt to learn too much too fast and get frustrated.

Amen, Walt, you are spot-on in your analysis of my situation. Haven't worked with linked lists yet. From what I understand, linked lists, memory allocation, and other "advanced" stuff will be covered in my upcoming 10 weeks of C++ classes. Believe it or not, it took 20 weeks to get me where I am now, and I'm not even a rookie yet!

BTW, the project is done 100% functional got an A.

:davis - having been a self taught programmer for 25 years (vb, sql, sqr), I decided I wanted to learn programming from the ground up. Showing initiative in an academic environment is ok to a point, but I want to learn C the right way and not skip over steps to accomplish a task. As stated above, functionality your speaking of is on the way, and by the way, Walt's response got me where I needed for my project and I learned a little more to add to my presently limited kowledgebase. Again, Walt's response was in context with where I am "supposed to be" at this point in my education. I think, in fact I'm sure that his respose would have been different if my example referenced more advanced data or data file manipulation functions. I thank you though for your comments and hope to be at the level you guys are at in the future!

Walt - call 'em like you see 'em!!!!

Cheers,
Mike M.

#9 31-Aug-2006, 22:36

Quote:

Originally Posted by wmmccoy0910

Walt - call 'em like you see 'em!!!!

Cheers,
Mike M.

So, do you have an example of your input file or not?

:davis:

wmmccoy0910 · #10 31-Aug-2006, 23:19

Quote:

Originally Posted by davis

So, do you have an example of your input file or not?

:davis:

Geesh!!!

So, did you see my post that stated my problem was solved, or did you even bother to read my previous ( and most current) post, where I even complimented you in spite of the fact that you were a bit harsh with the guy who REALLY helped me out?

Quote:

BTW, the project is done 100% functional got an A.

Please read the whole thread before posting inflamatory (and irrelevant) stuff, Ok?

Nothing personal, but relevant in this case.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
random access file read problem	wmmccoy0910	C Programming Language	13	19-Aug-2006 02:02
Download files in c for windows operating system	oozsakarya	C Programming Language	5	20-Jun-2006 03:33
CD burner wont burn!!	robertli55	Computer Hardware Forum	1	18-Jun-2004 10:53
Yet another CD burner problem: Lite-On LSC-24082K	Erwin	Computer Hardware Forum	1	22-May-2004 11:28

How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?

Re: How to sort random access file?