How does the compare function in qsort work?
I found this sample code online that explains how the function works qsort
. I couldn't figure out what the comparison 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;
}
source to share
int cmpfunc (const void * a, const void * b) //what is it returning?
{
return ( *(int*)a - *(int*)b ); //What is a and b?
}
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 );
}
source to share
What a
, and b
clearly stated in the documentation of qsort
: pointers that point to elements of the array that you want to compare.
The comparison function in this case knows that the elements of the array are of type int
. So it casts pointers void *
to int *
and performs a three-digit comparison on the pointed values int
by subtracting the second from the first.
It will work correctly for your set of values, but in general, using subtraction for a three-state comparison is bad programming practice as it is prone to overflow. Also, the function in your code example unnecessarily strips away the sharpened constant.
A better alternative would be
int cmpfunc(const void *a, const void *b)
{
const int *A = a, *B = b;
return (*A > *B) - (*A < *B);
}
source to share
Whenever the sorting algorithm needs to determine which of the two elements should be placed before the other, it will call the compare function and pass pointers to the two elements. Since you are sorting the values int
, the pointers actually point to int
, but the signature must accept void*
to be usable with any data type. Therefore, to get the actual value of the item a
should be referred to int*
, and then dereferenced - therefore *(int*)a
. The function must return a negative value if it a
should be placed before b
, a positive value if it b
should be placed beforea
, or zero if it doesn't matter what 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 b
from the value a
is sufficient if we want the largest numbers to come first.
source to share
From http://en.cppreference.com/w/cpp/algorithm/qsort
The function cmp
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 accepts pointers void
, so the function qsort
can be used with any data type. However, inside the function, cmp
you must explicitly specify a pointer to the actual data type.
source to share
qsort will give each pair it needs to compare against cmpfunc and uses its return value to see which one is larger, then sorts the array accordingly.
Basically, if the comparison function returns a positive result, it means that the first argument is greater than the second. Likewise, if it returns negative, then the second argument is larger.
In this example, we want to sort integers. So, we need to decide which one is larger when we compare two elements of a given array. To compare them, it is enough to perform the substitution operation, since the result is positive when a is greater, 0 if a and b are equal, and negative if b is greater.
source to share