Using qsort() to sort doubles in an array of structs

Question

I am using qsort() to sort double values in an array of structs in descending order. I have the following code:

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

typedef struct page {
   double val;
   int id;
} page;

int cmpfunc(const void *a, const void *b) {
  const page *pageA = (page*)a;
  const page *pageB = (page*)b;
  return -(pageA->val - pageB->val);
}

int main(void) {
  page array[5];
  int n;
  int i = 1;

for(n = 0; n < 5; n++) {
    array[n].id = i;
    i++;
}

array[0].val = 0.0608;
array[1].val = 0.2230; 
array[2].val = 0.1673;
array[3].val = 0.1442;
array[4].val = 0.2499;

printf("Before sorting\n");

for(n = 0; n < 5; n++) {
    printf("page id = %d, val = %lf \n", array[n].id, array[n].val);
}

qsort(array, 5, sizeof(page), cmpfunc);

printf("\nAfter sorting\n");

for(n = 0; n < 5; n++) {
    printf("page id = %d, val = %lf \n", array[n].id, array[n].val);
}

return 0;
}

I have tried using qsort() to sort integers and it has worked. However, when trying to sort doubles, my output is not sorted:

After sorting:

page id = 2, val = 0.223000

page id = 3, val = 0.167300

page id = 4, val = 0.144200

page id = 5, val = 0.249900

page id = 1, val = 0.060800

I am not sure why the output is not sorted properly. I have read posts online about sorting values in an array of structs and I believe that my comparison function is correct. Any insights would be really appreciated.

Note: A common code idiom recognized by various compilers to create efficient code is return (a > b) - (a < b); — chux
– chux, Commented Jul 23, 2018 at 3:23

klutt · Accepted Answer · 2018-07-23 02:04:41Z

3

It is because the compare function returns an integer. The result of -(pageA->val - pageB->val) will get rounded.

Switch to

if (pageA->val == pageB->val)
    return 0;
else if(pageA->val > pageB->val)
    return 1;
else
    return -1;

I believe that my comparison function is correct.

Protip here. If you only believe that a function is correct, then test it to make sure. You verified that the sorting does not work by printing the result. You could also have printed the outputs for the compare function.

edited Jul 23, 2018 at 2:04

answered Jul 23, 2018 at 1:54

klutt

31.7k19 gold badges65 silver badges114 bronze badges

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

2 Comments

ceno980 Over a year ago

I've read that when comparing two values 'a' and 'b' with qsort(), the function has to return a negative value if 'a' is to be placed before 'b', a positive value if 'a' is to be placed after 'b', and zero if 'a' and 'b' are equal. If 'a' > 'b' then the compare function will return 1, but if 'a' < 'b' instead the compare function will return 0. I'm confused about the case where 'a' < 'b', because in this case 'a' will be placed before 'b', but the compare function will return 0 and not -1. How will qsort() know to place 'a' before 'b' if the function doesn't return -1?

klutt Over a year ago

I fixed that. Small miss from me.

dave · Accepted Answer · 2018-07-23 01:59:10Z

So we can see that the array is being sorted (those ids have moved around). And the id and values are still matched correctly so qsort is moving the data around correctly (we don't have the sizeof wrong).

So our problem must be the comparison function we passed. Let's have a look:

int cmpfunc(const void *a, const void *b) {
  const page *pageA = (page*)a;
  const page *pageB = (page*)b;
  return -(pageA->val - pageB->val);
}

Returns an int and we are comparing doubles. The result of pageA->val - pageB->val is a double that then gets rounded to an int. That means it will sometimes round to zero (meaning equal) when those aren't equal.

So better is:

int cmpfunc(const void *a, const void *b) {
  const page *pageA = (page*)a;
  const page *pageB = (page*)b;
  if (pageA->val == pageB->val)
      return 0;
  else
      return (pageA->val > pageB->val ? 1 : -1);
}

Collectives™ on Stack Overflow

Using qsort() to sort doubles in an array of structs

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related