10

I found this sample code online, which explains how the qsort function works. I could not understand what the compare function returns.

#include "stdlib.h" int values[] = { 88, 56, 100, 2, 25 }; int cmpfunc (const void * a, const void * b) //what is it returning? { return ( *(int*)a - *(int*)b ); //What is a and b? } int main(int argc, _TCHAR* argv[]) { int n; printf("Before sorting the list is: \n"); for( n = 0 ; n < 5; n++ ) { printf("%d ", values[n]); } qsort(values, 5, sizeof(int), cmpfunc); printf("\nAfter sorting the list is: \n"); for( n = 0 ; n < 5; n++ ) { printf("%d ", values[n]); } return 0; }
Improve this question
4
  • 1
    They're integers being read from the array values. The function returns the value of a - b, which will be < 0 (a negative number) if a is smaller, 0 if they're equal, or > 0 (a positive number) if a is larger. Commented Dec 4, 2014 at 0:27
  • a compare function (actually a callback function) for qsort returns exactly the same values as strcmp() I.E. if first item less than second item return -1 if items match return 0 if first item greater than second item return 1 Commented Dec 4, 2014 at 3:33
  • @user3629249: be careful not to test for the specific values -1 or 1: strcmp() (or the comparison function passed to qsort()) is allowed to return any negative or positive values for those cases. Commented Dec 5, 2014 at 22:39
  • 6
    This comparison function is bad, never use it. Suppose, you're sorting -1500000000 and 1500000000. The result of subtraction is -3000000000 which is not representable in int, hence the behaviour is undefined. What is worse, the usual behaviour of generated code is to wrap this to a positive number 1294967296, which completely breaks the sort. See AnT's answer for the one that works correctly and this QA for what can happen if you use this comparison function Commented Dec 18, 2018 at 4:17

6 Answers 6

Reset to default
11

What a and b are is clearly stated in the documentation for qsort: these are pointers that point to array elements that have to be compared.

Comparison function in this case knows that the array elements are of type int. So it casts the void * pointers to int * type and performs a tri-state comparison of the pointed int values by subtracting the second from the first.

It will work properly for your set of values, but in general case using subtraction for tri-state comparison is a bad programming practice, since it is prone to overflow. Also, the function in your sample code unnecessarily casts away the constness of the pointed values.

A better alternative would be 

int cmpfunc(const void *a, const void *b) { const int *A = a, *B = b; return (*A > *B) - (*A < *B); }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

8 
int cmpfunc (const void * a, const void * b) //what is it returning? { return ( *(int*)a - *(int*)b ); //What is a and b? }

Is equivalent to:

int cmpfunc (const void * a, const void * b) //what is it returning? { // qsort() passes in `void*` types because it can't know the actual types being sorted // convert those pointers to pointers to int and deref them to get the actual int values int val1 = *(int*)a; int val2 = *(int*)b; // qsort() expects the comparison function to return: // // a negative result if val1 < val2 // 0 if val1 == val2 // a positive result if val1 > val2 return ( val1 - val2 ); }
Improve this answer

2 Comments

This compare function will integer overflow if asked to compare large numbers whose signs differ. It should be avoided in production code. (At a minimum.) See stackoverflow.com/questions/53821538/… for someone who encountered problems when they tried to usr it.
See AnT's answer for the one that works correctly
2

Whenever the sorting algorithm needs to find out which of two elements should be placed before the other, it will call the comparison function and pass pointers to the two elements. Since you are sorting int values, the pointers are actually pointers to int, but the signature must take void* so that it can be used with any data type. Therefore, in order to obtain the actual element value, a must be cast to int* and then be dereferenced - hence, *(int*)a. The function must return a negative value if a is to be placed before b, a positive value if b is to be placed before a, or zero if it doesn't matter which is placed first (which is usually the case when the elements are equal). In this particular case, since we are working with numbers, simply subtracting the value of b from the value of a is sufficient if we want the biggest numbers to go first.

Improve this answer

Comments

2

From http://en.cppreference.com/w/cpp/algorithm/qsort

The cmp function returns ​a negative integer value if the first argument is less than the second, a positive integer value if the first argument is greater than the second and zero if the arguments are equal.

The function takes void pointers so the qsort function may be used with any data type. However inside the cmp function you must explicitly cast the pointer to the actual data type.

Improve this answer

Comments

1

a and b are being compared as integers - they have to be passed in as void * but are then cast to int * before finally being deferenced. As for the return value, it will either be positive, negative, or zero, all of which would be taken into account in the sorting function.

Improve this answer

Comments

0

qsort will give each pair it needs to compare to cmpfunc and uses it's return value to see which one is greater and then sorts the array accordingly.

Basically, if the compare function returns a positive result this means that the first argument is greater than the second one. Similarly, if it returns negative, then the second argument is greater.

In the example, we want to sort integers. So, we need to decide which one is greater when we compare two elements of the given array. To compare those, a simple substraction operation is enough since the result is positive when a is greater, 0 if a and b are equal and negative if b is greater.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.