qsort() in array of structure in C

Question

I am trying to sort the array of structure which takes 20 inputs and sort them using C's standard library function qsort() but not getting proper sorted output.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#pragma pack(1)
struct player{
    char name[4];
    short age;
    short match;
    float average;
};
#pragma pack()
int comp(const void *p,const void *q){
    float *a=(float*)p;
    float *b=(float*)q;
    if(*b-*a>0)return 1;
    if(*b-*a<0)return 1;
    if(*b-*a==0)return 0;
}
int main(){
    struct player list[20];
    for(int i=0;i<20;i++){
        scanf("%s",list[i].name);       
        scanf("%hu %hu %f",&list[i].age,&list[i].match,&list[i].average);
    }
    qsort((void*)list,20,sizeof(struct player),comp);
    for(int i=0;i<20;i++){
        printf("%2.2f %10s %4hu %4hu\n",list[i].average,list[i].name,list[i].age,list[i].match);
    }
    return 0;
}

one may use the following test case to check there output.

aaa 21  22  34
qsd 33  21  44
qqq 1   2   55.2
www 33  22  12.2
ewe 22  11  13.3
qaz 22  33  12.33
aaa 21  22  34
qsd 33  21  44
qqq 1   2   54.2
www 33  22  12.2
eee 22  11  16.3
qaz 22  33  18.33
aaa 21  22  34
qsd 33  21  49
qqq 1   2   52.2
www 33  22  12.2
eee 22  11  10.3
qaz 22  33  11.33
eee 22  11  14.3
qaz 22  33  11.33

Why your `comp` is trying to interpret the passed pointers as `float*`? — Eugene Sh., Jul 22 '19 at 17:27
`const void *p` does not point to `float` but to the whole `struct` element of the array. So the `comp` function can first cast the arguments to the correct type, and then compare members of the `struct`s. — Weather Vane, Jul 22 '19 at 17:27

Gereon · Answer 1 · 2019-07-22T17:34:11.723

2

Use a compare function like this:

int comp(const void *p, const void *q) {
  struct player *p1 = (player*)p;
  struct player *p2 = (player*)q;

  if (p1->average > p2->average) return 1;
  if (p1->average < p2->average) return -1;
  return 0;
}

edited Jul 22 '19 at 17:34

answered Jul 22 '19 at 17:32

Gereon

17,258
4
42
73

Why not replace `if`s with `return p1->average - p2->average`? More concise and is the norm for comparison functions – Jonathan Lam Jul 22 '19 at 17:37
1

@JonathanLam because that can overflow. It's typical, but faulty. – Weather Vane Jul 22 '19 at 17:37
3

Not (only) that. The difference can be less than one, but then it is cast to `int` – Eugene Sh. Jul 22 '19 at 17:38
@JonathanLam think twice, that can't be true, a utopia, to say the least... :) – gsamaras Jul 22 '19 at 17:44

gsamaras · Answer 2 · 2019-07-22T17:53:14.237

Your custom comparison method should look like this:

int comp(const void *p, const void *q) {
  struct player *a = (struct player*)p;
  struct player *b = (struct player*)q;

  if(b->average > a->average)
    return 1;
  else if (b->average < a->average)
    return -1;
  else
    return 0;
}

As @EugeneSh. and @WeatherVane commented, the parameters of that method are pointers to structs - for example the first element of your array will be pointed by p and the second by q at a certain comparison.

So, you first need to cast to a pointer to the struct, and then use its field to perform the actual comparison.

Now the comparison has a logical flaw as @Gereon and I commented: It returns 1 in the less AND in the greater case, which is surely not what you want. Return 1 in one case, and -1, for example, in the other case.

As for the return 0; case, it's good as it is, ensuring a stable sort.

Tip: Do not be tempted to use return p1->average - p2->average, as typically illustrated in the ref's example, since you are dealing with floats, and the least thing you need is a numerical instability, since it can overflow. Moreover, the difference can be less than one, but then it is cast to int.

@WeatherVane we just practiced the paradigm of maieutics, introduced by Socrates 25 centuries ago.. Thanks guys (+EugeneSh.), you helped me improve my answer! — gsamaras, Jul 22 '19 at 17:38
@EugeneSh. well there is the infinity representation, but if the values are very small, their difference might be `0.0` when it is not. Integers don't have that, so best to use a foolproof method all the time. — Weather Vane, Jul 22 '19 at 17:45

qsort() in array of structure in C

2 Answers2