How does the compare function in qsort work?

Question

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;
}

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. — Ken White, Dec 04 '14 at 00: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 — user3629249, Dec 04 '14 at 03: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. — Michael Burr, Dec 05 '14 at 22:39
**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](https://stackoverflow.com/a/27284248/918959) and [this QA for what can happen if you use this comparison function](https://stackoverflow.com/q/53821538/918959) — Antti Haapala -- Слава Україні, Dec 18 '18 at 04:17

score 9 · Answer 1 · answered Dec 04 '14 at 00:31

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);
}

score 7 · Accepted Answer · answered Dec 04 '14 at 00:38

7

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 ); 
}

answered Dec 04 '14 at 00:38

Michael Burr

333,147
50
533
760

5

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 https://stackoverflow.com/questions/53821538/possible-bug-in-std-c-quicksort-am-i-missing-something for someone who encountered problems when they tried to usr it. – rici Dec 18 '18 at 02:00
[See AnT's answer for the one that works correctly](https://stackoverflow.com/a/27284248/918959) – Antti Haapala -- Слава Україні Dec 18 '18 at 04:04

score 2 · Answer 3 · answered Dec 04 '14 at 00:27

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.

score 2 · Answer 4 · answered Dec 04 '14 at 00:27

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.

score 1 · Answer 5 · answered Dec 04 '14 at 00:26

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.

score 0 · Answer 6 · answered Dec 04 '14 at 00:36

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.

How does the compare function in qsort work?

6 Answers6

Linked

Related