• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 358
  • Last Modified:

Help sorting informations from an array of structs

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
The_Kingpin08
Asked:
The_Kingpin08
  • 10
  • 9
  • 4
  • +2
1 Solution
 
brettmjohnsonCommented:
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
 
The_Kingpin08Author Commented:
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
 
lbertaccoCommented:
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
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
hanhvansuCommented:
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
 
Julian HansenCommented:
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
 
Julian HansenCommented:
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
 
The_Kingpin08Author Commented:
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
 
The_Kingpin08Author Commented:
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
 
lbertaccoCommented:
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
 
lbertaccoCommented:
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
 
Julian HansenCommented:
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
 
The_Kingpin08Author Commented:
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
 
Julian HansenCommented:
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
 
The_Kingpin08Author Commented:
yes thanks a lot julianH !
0
 
The_Kingpin08Author Commented:
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
 
The_Kingpin08Author Commented:
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
 
The_Kingpin08Author Commented:
qsort(books, num_books, sizeof(bookInfo) * 2, compare );
0
 
Julian HansenCommented:
No problem - glad to have been of help.
0
 
The_Kingpin08Author Commented:
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
 
Julian HansenCommented:
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
 
Julian HansenCommented:
Oops - mistake - you can loose the second line
 bookinfo * pBook
it is not needed
0
 
Julian HansenCommented:
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
 
The_Kingpin08Author Commented:
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
 
Julian HansenCommented:
My pleasure - glad to have been of help
0
 
lbertaccoCommented:
Note that in the 3rd paramter to qsort you have to use
 sizeof(bookInfo)
and not
 sizeof(bookInfo) * 2
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 10
  • 9
  • 4
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now