How to sort a struct with strings using its integers in C?

Question

I'm coding a program in C that should rank countries by its gold medals in the olympic games.

Here's the code:

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

typedef struct _Table {
    char *country;
    int amnt, gold, silver, bronze;
} Table;

char *arrayAlloc(int size) {
    char *array;
    array = (char *) malloc(sizeof(char) * size);
    return array;
}

void readTable(Table *ptr) {
    char buffer[100], *cpyPtr, *savePtr;
    for (int i = 0; i < ptr->amnt; ++i) {
        fgets(buffer, sizeof(buffer), stdin);
        buffer[strlen(buffer) - 1] = '\0';  
        ptr[i].country = strtok_r(buffer, " ", &savePtr);
        ptr[i].country = strdup(ptr[i].country);            
        cpyPtr = strtok_r(NULL, " ", &savePtr);
        ptr[i].gold = strtol(cpyPtr, &cpyPtr, 10);
        cpyPtr = strtok_r(NULL, " ", &savePtr);
        ptr[i].silver = strtol(cpyPtr, &cpyPtr, 10);
        cpyPtr = strtok_r(NULL, " ", &savePtr); 
        ptr[i].bronze = strtol(cpyPtr, &cpyPtr, 10);
    }

}

void printTable(Table *ptr) {
    for (int i = 0; i < ptr->amnt; ++i) {
        printf("%s %d %d %d\n", ptr[i].country, ptr[i].gold,ptr[i].silver, ptr[i].bronze);
    }
}

int compare(const void *p, const void *q) {
    int l = ((Table *)p)->gold;
    int r = ((Table *)q)->gold; 
    return (r - l);
}


int main(int argc, char const *argv[]) {
    int N;      // Amount of lines
    scanf("%d", &N);
    getchar();
    Table tab[N];
    tab->amnt = N;
    tab->country = arrayAlloc(100);

    readTable(tab);

    qsort(&tab->gold, tab->amnt, sizeof(Table), compare);

    printTable(tab);

    free(tab->country);
    return 0;
}

Input example:

4
BRA 3 4 5
USA 23 76 34
CHN 23 54 12
GER 10 20 23

Expected output:

USA 23 76 34
CHN 23 54 12
GER 10 20 23
BRA 3 4 5

What I'm getting:

BRA 23 54 12
GER 23 76 34
CHN 3 4 5
USA 10 20 23

As you can see it seems to "sort" it somehow. However it is far from what I need to accomplish. I've already tried to modify the compare() function, but without success. What am I possibly missing here?

The variable tab is an array. It's this array you should sort, not the first elements gold member. The expression tab->gold is equal to tab[0].gold. — Some programmer dude
– Some programmer dude, Commented Jun 14, 2017 at 11:40
Your minimal reproducible example is full of bugs, your question become too broad. — Stargateur
– Stargateur, Commented Jun 14, 2017 at 11:49
Thank you @Stargateur, next time I'll follow the instructions from this link. — Rogers S. Cristo
– Rogers S. Cristo, Commented Jun 14, 2017 at 12:04

ilkkachu · Accepted Answer · 2017-06-14 12:09:03Z

3

qsort(&tab->gold, tab->amnt, sizeof(Table), compare);

The first two arguments should be a pointer to your array (Table tab[N];) and the number of elements in the array (N), i.e.:

qsort(tab, N, sizeof(Table), compare);

You did have the correct number of elements in tab->amnt, but the start pointer &tab->gold doesn't point to the beginning of the table, but in the middle of the first element, so qsort can't work correctly.

Also, you have functions with loops like this:

void printTable(Table *ptr) {
    for (int i = 0; i < ptr->amnt; ++i) {

Which means that you're carrying the size of the array in its first member. That seems odd, and means the array member 'amnt' is redundant in all but the first member of the array.

But if the array gets sorted, the first array member is no longer the first, and ptr->amnt doesn't contain the correct size any longer.

Better change printTable to

void printTable(Table *ptr, unsigned size) {
    for (int i = 0; i < size; ++i) {

and call it with

printTable(tab, N);

Same for readTable.

I'm also not sure what the purpose of this is:

tab->country = arrayAlloc(100);

You're preallocating space pointed to by the country pointer in the first array member, but in any case readTable allocates space for country with strdup to all array members.

You might also want to consider checking the value or N entered by the user, or allocating the memory for tab via malloc. Now tab is allocated on the stack, which may cause the program to crash if the user enters some number large to cause a stack overrun.

Also, since you don't check the return values of the strtok_r calls in readTable, the program will crash if the user gives malformed input.

edited Jun 14, 2017 at 12:09

answered Jun 14, 2017 at 11:41

ilkkachu

6,56418 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

P0W Over a year ago

There are still other issues as well

ilkkachu Over a year ago

@Stargateur, well, they sort of work, as long as the sort doesn't. But you're right, I only looked at the sorting step first, that seemed to be the issue based on the example output.

Rogers S. Cristo Over a year ago

Thank you @ilkkachu, it worked fine after your suggested modifications. Also, I did not know I can't pass ptr->amnt this way. Thank you very much!

Stephan Lechner · Accepted Answer · 2017-06-14 12:08:21Z

There are several issues; yet the main two are the following:

In qsort(&tab->gold, tab->amnt, sizeof(Table), compare), you do not pass the begin of the array (as neccessary), but a pointer to a data member of the first element in the array. This means that the pointer passed has a particular offset to the begin of the array and will point almost in the "middle" of the first element. As qsort will exchange elements (i.e. memory chunks of the size provided) relative to the pointer you provide to qsort, each object may get "split" with unexpected and weird results then (very likely yielding undefined behaviour as well).

Second, you use tab->amnt = N, which is equivalent to tab[0].amnt = N, i.e. it sets amnt only for the first entry. If you then sort the array, the first entry may be replaced by another one, which does not have set amnt to a specific value. So your print-function, which again relies on amnt being in the first element, will count wrong.

So write qsort(tab, N, sizeof(Table), compare) and manage the size of the array outside the elements, i.e. introduce a separate parameter size, that is then passed to the print-function.

Maybe there are other issues as well, but these two are the most suspicious ones to me.

Davide Spataro · Accepted Answer · 2017-06-14 13:32:20Z

0

There is more than one issue in your code.

First if all you your tab would be better if allocated dynamically.

Table* tab = malloc(sizeof(Table)*N);

Variable-length array are only supported by c99 and later versions and some C11 implementation might not support them too if __STDC_NO_VLA_ is defined (Check C11 standard 6.10.8.3)

Secondly, everything which iterates on tab has to know tab's size which's N that you have to pass around as for instance in

void readTable(Table *ptr, const int N) {
    char buffer[100], *cpyPtr, *savePtr;
    for (int i = 0; i < N; ++i) {...

Finaly qsort need to be called as follows:

 qsort(tab, N,sizeof(Table), compare);

The following will produces the expected output (note that I have not checked for any other issues):

typedef struct _Table {
    char *country;
    int amnt, gold, silver, bronze;
} Table;

char *arrayAlloc(int size) {
    char *array;
    array = (char *) malloc(sizeof(char) * size);
    return array;
}

void readTable(Table *ptr, const int N) {
    char buffer[100], *cpyPtr, *savePtr;
    for (int i = 0; i < N; ++i) {
        fgets(buffer, sizeof(buffer), stdin);
        buffer[strlen(buffer) - 1] = '\0';  
        ptr[i].country = strtok_r(buffer, " ", &savePtr);
        ptr[i].country = strdup(ptr[i].country);            
        cpyPtr = strtok_r(NULL, " ", &savePtr);
        ptr[i].gold = strtol(cpyPtr, &cpyPtr, 10);
        cpyPtr = strtok_r(NULL, " ", &savePtr);
        ptr[i].silver = strtol(cpyPtr, &cpyPtr, 10);
        cpyPtr = strtok_r(NULL, " ", &savePtr); 
        ptr[i].bronze = strtol(cpyPtr, &cpyPtr, 10);

    }

}

void printTable(Table *ptr, const int size) {
    for (int i = 0; i < size; ++i) {
        printf("%s %d %d %d\n", ptr[i].country, ptr[i].gold,ptr[i].silver, ptr[i].bronze);
    }
}

int compare(const void *p, const void *q) {

    return ((Table *)p)->gold<((Table *)q)->gold;
}


int main(int argc, char const *argv[]) {
    int N;      // Amount of lines
    scanf("%d", &N);
    getchar();
     Table* tab = malloc(sizeof(Table)*N);


    readTable(tab,N);
    printTable(tab,N);
    qsort(tab, N,sizeof(Table), compare);

    printTable(tab,N);

    free(tab);
    return 0;
}

outputs:

BRA 3 4 5
USA 23 76 34
CHN 23 54 12
GER 10 20 23

USA 23 76 34
CHN 23 54 12
GER 10 20 23
BRA 3 4 5

edited Jun 14, 2017 at 13:32

answered Jun 14, 2017 at 11:55

Davide Spataro

7,5321 gold badge28 silver badges37 bronze badges

4 Comments

mch Over a year ago

Why should tab be dynamically allocated?

chux Over a year ago

Consider qsort(tab, N, sizeof *tab, compare);. No need to look back to tab definition to see if sizeof(Table) is correct. Also Table* tab = malloc(sizeof *tab * N);, just like code used the size of the object rather than the size of the type in fgets(buffer, sizeof(buffer), stdin);

chux Over a year ago

BTW, buffer[strlen(buffer) - 1] = '\0'; can be exploited by a user entering a null character as the first character read by fgets(). Suggest buffer[strcspn(buffer, "\n")] = '\0';

Davide Spataro Over a year ago

I personally think that the code is much clearer when sizeof is used with an explicit type. Regarding the dynamic allocation, I've edited the answer. Thanks for the suggestions.

Collectives™ on Stack Overflow

How to sort a struct with strings using its integers in C?

3 Answers 3

3 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related