Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Help sorting informations from an array of structs

Posted on 2004-10-26
25
Medium Priority
?
355 Views
Last Modified: 2012-05-05
Hi everybody, I've started a project not far ago and I'm and now starting the last part.

I've previously programmed an array that contains structs, each structs containing different information. I must now take these informations and sort them to print a cute little list. The problem is that I need to print 2 differents lists, each using the quicksort method to sort the array on different record of a struct, but 1 ascending and the other decreasing.

Now the reason I'm posting this is to get some advices on the best way to understand and solve this problem. I don't have a large knowledge of C language so every help would be appreciated. Should I start by programming a quicksort function taking an array of struct or reading every struct of the array individually and  ? Which step should I take first ? Right now it's looking like a giantic task for me butonce I plan the correct steps I hopw it will get easier !

Here my main struct just for the record:
 struct book
 {
     char title[80];
     char autor[40];
     char editor[20];
     char ISBN[10];
     char subject[20];
     char releaseDate[10];
 };
typedef struct book bookInfo;

and here's my array of struct:
bookInfo *books = NULL;


Thanks all for your time.
Frank
0
Comment
Question by:The_Kingpin08
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 9
  • 4
  • +2
25 Comments
 
LVL 23

Expert Comment

by:brettmjohnson
ID: 12418593
Why resort the array to get descending?  Once you sort the array in ascending order,
simply traverse the array in reverse to display descending order:

/* print the list in descending order */
for (i = arrayCount-1; i >= 0; i--)
      printBook(&array[i]);

0
 

Author Comment

by:The_Kingpin08
ID: 12418625
One list has to be ascending based on the Subject record while the other list has to be descending based on the releaseDate record.
besides that, any ideas on how to create the quicksort using informations from a struct's field inside an array ?
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 12419303
You can use the stdlib.h library function qsort().

#include <stdlib.h>

int relDatRevCmp(void *a, void *b)
{
  return -strcmp(((bookInfo *)a)->releaseDate, ((bookInfo *)b)->releaseDate);
}

main()
...
qsort(books, arrayCount, sizeof(bookInfo), relDatRevCmp);
...

This is assuming that you want a lexicographical sort on the releaseDates and that these are zero terminated strings; but you can easily modify it for different situations.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Expert Comment

by:hanhvansu
ID: 12419417
Hi The_Kingpin08 !

The simplest way to solve your problem is writting 2 functions,one for ascending the array based on Subject and the other for descending the array based on releaseDate! If you want to know the code of quicksort , just let me know !

Have fun!
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12419818
If I understand you correctly you want the following
 
Field1    Field2
A             3
A             2
A             1
B             5
B             1
C             2
C             1
C             0

In your compare function for qsort simply do the following

if (s1.field1 < s2.field1 ) return -1 ;
if (s1.field1 > s2.field1)  return 1 ;

// If we get here s1.field1 == s2.field1 so compare on field2 remember to switch the return value around to do descending sort.

if (s1.field2 < s2.field2) return 1;
if (s2.field2 > s2.field2) return -1 ;

// If we get here s1.field1 == s2.field1 and s1.field2 = s2.field2 so return 0 to indicate equal.

return 0;

Haven't tested it yet but give it a go.
0
 
LVL 59

Accepted Solution

by:
Julian Hansen earned 2000 total points
ID: 12419853
Here is some sample code that demonstrates the point

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef struct
{
      int field1 ;
      int field2 ;
} S ;

S ms[] = {
      {5,3},
      {4,1},
      {1,2},
      {3,3},
      {5,1},
      {2,2},
      {2,1},
      {2,3},
      {1,3},
      {4,2},
      {1,1},
      {3,2},
      {2,3},
      {1,4}
} ;

int compare( const void *arg1, const void *arg2 );

void main( int argc, char **argv )
{
   int i;
   /* Eliminate argv[0] from sort: */
   argv++;
   argc--;

   /* Sort remaining args using Quicksort algorithm: */
   qsort( (void *)ms, 14, sizeof( int ) * 2, compare );

   /* Output sorted list: */
   for( i = 0; i < 14; ++i )
      printf( "%d %d \n", ms[i].field1, ms[i].field2 );
   printf( "\n" );
}

int compare( const void *arg1, const void *arg2 )
{
      S *s1 = (S*)arg1;
      S *s2 = (S*)arg2;

      if ( s1->field1 < s2->field1 ) return -1 ;
      if ( s1->field1 > s2->field1 ) return 1 ;

      if ( s1->field2 < s2->field2 ) return 1 ;
      if ( s1->field2 > s2->field2 ) return -1 ;

      return 0 ;
}
0
 

Author Comment

by:The_Kingpin08
ID: 12420438
Damn and me that already started programming a quicksort function not knowing the stdlib.h included one ! julianH, would it be possible to use your way but get the information from struct inside an array ? Here's what I think it would looks like with my function.

BTW do we need to create a compare function to use the built-in qsort ?

 /* Struct containing the informations on a book */
 struct book
 {
     char title[80];
     char autor[40];
     char editor[20];
     char ISBN[10];
     char subject[20];
     char releaseDate[10];
 };
 typedef struct book bookInfo;

int main()
 {
   FILE *file;                           // File containing the data
   bookInfo *books = NULL;     // Array of books, UNKNOWN size
   char buff[10000];                // Buffer to read in the file
   int i =0;
   int num_books = 0;             // Keep the count of number read in
   int line_number = 0;           /* Used to count the 6 lines required
                                           to create a new struct */
   argv++;                            /* Eliminate argv[0] from sort: */
   argc--;

 
   /* First step we open the file and see if it's correct */
   file = fopen("livres.txt", "r");
   if(file==NULL)
      {
      printf("Error: can't open file.\n");
      return 1;
      }
   else
      {
        /* First loop that goes through every line of the file */
      while(fgets(buff, sizeof(buff), file) != NULL)
        {
                  bookInfo BOOK; // Create a new book

                  /* Resize the array containing the structs */
                  parseline(&BOOK, buff, line_number);
                  if(line_number==5)
                  {
                        void *temp = realloc( books, (num_books + 1) * sizeof(bookInfo));
                        if ( temp != NULL )
                        {
                              books = (bookInfo*)temp;
                        }
                        
                        /* Sort remaining args using Quicksort algorithm: */
                        qsort( (void *)BOOK, 14, sizeof( int ) * 2, compare );

                               /* Output sorted list: */
                              for( i = 0; i < 14; ++i )
                              printf( "%d %d \n", books[i].title, books[i].autor);
                              printf( "\n" );
...


int compare( const void *arg1, const void *arg2 )
{
     BOOK *book1 = (BOOK*)arg1;
     BOOK *book2 = (BOOK*)arg2;

     if ( book1 ->title< book2 ->title) return -1 ;
     if ( book1 ->title> book2 ->title) return 1 ;

     if ( book1 ->autor< book2 ->autor) return 1 ;
     if ( book1 ->autor> book2 ->autor) return -1 ;

     return 0 ;
}


Thanks, Frank

0
 

Author Comment

by:The_Kingpin08
ID: 12420481
I don't really understand how this built-in qsort function works... If someone could be kind enough to at least tell me the parameters it requires then I could discovr the rest :)

Frank
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 12420526
You NEED to create a compare function unless the ones already in the library are fine for you (e.g. strcmp which just compare 2 strings)

In your code above here, you cannot do:
 if ( book1 ->title< book2 ->title) return -1 ;
since these are strings and you cannot compare strings with "<" in C, but you have to use strcmp.

So you could do
int compare( const void *arg1, const void *arg2 )
{
     BOOK *book1 = (BOOK*)arg1;
     BOOK *book2 = (BOOK*)arg2;
     int t=strcmp(book1->title, book2->title);
     if(t) return t;
     return strcmp(book1->autor, book2->autor);
}
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 12420605
Oops, I didn't check the rest of your code but there seem to be other issues there too.
Why were you using BOOK *book1 ? Your book type is bookInfo, not BOOK, so:

int compare( const void *arg1, const void *arg2 )
{
     bookInfo *book1 = (bookInfo *)arg1;
     bookInfo *book2 = (bookInfo *)arg2;
     int t=strcmp(book1->title, book2->title);
     if(t) return t;
     return strcmp(book1->autor, book2->autor);
}

Also when you call qsort, the second argument is the number of elements in the array (num_books?), not 14; and the third element is the size of an element, that is sizeof(bookInfo), not sizeof(int)*2.
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12420681
The_Kingpin08,

To expand on what lbertacco says above.

The compare function is necessary because the qsort algorithm does not know anything about the data you are trying to sort integers, strings etc. You need to provide a function that tells qsort how to elements relate to each other with respect to ranking. QSort will call your compare function each time it wants to know how two elements compare with each other and based on what the function returns qsort will make a decision about how to deal with the two elements.

lbertacco's compare function above should do it except for one small error. You want to sort descending on the autor field so you need to swap the parameters arround in the strcmp i.e instead of

   return strcmp(book1->autor, book2->autor);

do

   return strcmp(book2->autor, book1->autor);

The strcmp function returns a value < 0 if str1 < str2, ==0 if they are the same and >0 if str1 > str2. This is what the compare function should return as well so it is a simple matter to just return the return value of strcmp - however the order you put the parameters in is important to determine the sort order.


0
 

Author Comment

by:The_Kingpin08
ID: 12420731
hey thanks a lot guys, your support is so precious.

There's one other thing I don't understand and that's the use of "argv" I've already seen this in VB and Java I think but can't remember it's function and it's use in this case.

Thanks again. Frank
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12420829
Not sure what you are referring to. In C/C++ there is a convention for accessing command line parameters

int main ( int argc, char* argv[])

where argv is an array of strings storing the command line parameters with argv[0] being the path and filename of the executable and each element of the array corresponding to 1 space or "" delimited word entered on the command line.

However this is just a convention and could just as easily be

int main (int Fish, char* AndChips[])
{
   int i ;
   for ( i = 0 ; i < Fish ; i++ ) printf ( "Argument[%d] = %s\n", i, AndChips[i] ) ;

   return 0;
}

Not elegant but syntactically correct ... ;)

Don't know if that answers your question.
0
 

Author Comment

by:The_Kingpin08
ID: 12420847
yes thanks a lot julianH !
0
 

Author Comment

by:The_Kingpin08
ID: 12420876
When I tried calling the qsort function with my line

qsort( (void *)BOOK, num_books, sizeof(bookInfo) * 2, compare );

I get 2 errors:

-Cannot convert from 'bookInfo' to 'void *'
-too few arguments for call through pointer-to-function

is the first parameter correct ? I still don't know what the first parameter refer to...

Thanks a thousand time,

Frank
0
 

Author Comment

by:The_Kingpin08
ID: 12420903
ok I found out that the first parameter is the list, so I changed it to

qsort( (void *)BOOK, num_books, sizeof(bookInfo) * 2, compare );


Thanks all for your support !

Frank
0
 

Author Comment

by:The_Kingpin08
ID: 12420945
qsort(books, num_books, sizeof(bookInfo) * 2, compare );
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12420958
No problem - glad to have been of help.
0
 

Author Comment

by:The_Kingpin08
ID: 12421000
Ok now I've ran into another proble :(  (can't wait until this project is over so I can sleep!)

Looks like my Compare function isn't correct. It never does seem to find the second argument, the *book2. How could I specify that the 2nd item to read is the 2 value of the struct array named "books" which is a bookInfo type ? Is this possible ?

int compare( const void *arg1, const void *arg2 )
{
     bookInfo *book1 = (bookInfo *)arg1;
     bookInfo *book2 = (bookInfo *)arg2;
     int t=strcmp(book1->title, book2->title);
     if(t) return t;
     return strcmp(book1->autor, book2->autor);
}
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12421250
Hi Kingpin,

I am not sure what you are asking here - the compare function does appear to be correct when you say it is not finding the second argument - what exactly do you mean?

The only problem with the compare function is the last line which should be corrected as per my earlier post to ensure the descending sort on the autor field.

Ok, just took a look at your code. You are looping reading records from the file into the variable BOOK - 1 instance of the structure. You are then reallocing a pointer variable (your array) and setting book equal to this array. Here is the problem

Firstly you are passing BOOK to the qsort function which will never work because it will always only contain 1 record.
Secondly, after parsing the record into BOOK and reallocating the book pointer you are never copying the new record into the array.

You should be doing something along the lines of


bookinfo * bookarray ;
bookinfo * pBook ;
int cp = 0 ;
int size = 10 ;

bookarray = malloc ( sizeof(bookinfo*) * size ) ; // Make provision for a 10 element array
// open the file here
while (fgets (buffer,BUFFSIZE,file) )
{
   if ( cp == size )
   {
       size = size + 10 ;
       bookarray = realloc ( bookarray, sizeof(bookinfo*) * size ) ;
   }

   bookarray[cp] = malloc ( sizeof ( bookinfo ) );
   parseline (bookarray[cp], buff ) ;
}

// close file here
qsort ( ( void *) bookarray, cp, sizeof(bookinfo), compare ) ;

for ( int i = 0 ; i < cp; i++ ) printf ...

// free memory here

I have not tested the code but that is the gist of it.
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12421257
Oops - mistake - you can loose the second line
 bookinfo * pBook
it is not needed
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12421291
Oops nuther error - cp not being incremented - see revised code

bookinfo * bookarray ;
int cp = 0 ;
int size = 10 ;

bookarray = malloc ( sizeof(bookinfo*) * size ) ; // Make provision for a 10 element array

// open the file here

while (fgets (buffer,BUFFSIZE,file) )
{
   // check to see if array is full ...
   if ( cp == size )
   {
       size = size + 10 ; // make provision for another 10 elements - arbitary selection
       bookarray = realloc ( bookarray, sizeof(bookinfo*) * size ) ; // resize the array keeping existing elements
   }

   bookarray[cp] = malloc ( sizeof ( bookinfo ) ); // create a new record in the next available position in the array for the new record
   parseline (bookarray[cp], buff ) ;   // fill in the record data
   cp++ ;   // increment your array pointer and go around again
}

// close file here
qsort ( ( void *) bookarray, cp, sizeof(bookinfo), compare ) ;

for ( int i = 0 ; i < cp; i++ ) printf ...

// free memory here
0
 

Author Comment

by:The_Kingpin08
ID: 12421572
Alright, thhanks a lot julianH, your last reply help me solve my problem. I didn't use your code but understod it to correct some mistakes I made in my code...

Thanks a thousand time again, now I can almost see the rest coming !

Frank
0
 
LVL 59

Expert Comment

by:Julian Hansen
ID: 12421622
My pleasure - glad to have been of help
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 12424098
Note that in the 3rd paramter to qsort you have to use
 sizeof(bookInfo)
and not
 sizeof(bookInfo) * 2
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
In this post we will learn different types of Android Layout and some basics of an Android App.
Starting up a Project
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

610 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question