# 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;

Frank
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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 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
Commented:
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
Commented:
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
Commented:
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
Commented:
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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author 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
Author 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
Commented:
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
Commented:
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
Commented:
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 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
Commented:
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 ... ;)

0
Author Commented:
yes thanks a lot julianH !
0
Author 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
Author 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
Author Commented:
qsort(books, num_books, sizeof(bookInfo) * 2, compare );
0
Commented:
No problem - glad to have been of help.
0
Author 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
Commented:
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
Commented:
Oops - mistake - you can loose the second line
bookinfo * pBook
it is not needed
0
Commented:
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 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
Commented:
My pleasure - glad to have been of help
0
Commented:
Note that in the 3rd paramter to qsort you have to use
sizeof(bookInfo)
and not
sizeof(bookInfo) * 2
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.