Csdrhrt

I have read that the comparison function required by qsort() needs to have 3 outcomes:

• a negative result if val1 < val2
  


• 
  0 if val1 == val2
  


• a positive result if val1 > val2
  

As far as I know, sorting an array only requires a predicate that returns true or false. Take bubble sort for example:

int compare(int a, int b)

{

    if(a>b) return 1;

    return 0;

}

void bubbleSort(int arr, int n) 

{

    int i, j;

    for (i = 0; i < n-1; i++)  

        for (j = 0; j < n-i-1; j++)  

            if ( compare(arr[j],arr[j+1]) ) 

                swap(&arr[j], &arr[j+1]);

}

So why does the qsort() comparison function need to have 3 possible outcomes and not 2?

Based on the comment of @Matteo Italia, there is an efficiency issue in the number of comparison and you can reduce the number of comparison using the equality as a == b and !(a < b) && !(b < a) are equivalent in some cases (for example when the values are integer).

Also, in more general case (not in qsort specifically as mentioned in comments), you need it for stability of the sort function. In equality cases, if the sort wants to be stable, it should know about the equality in the comparison. You can know more about the stabilty in sorting here.
Hence, three value return is required for stable sort methods.

qsort could be written using a boolean compare function instead of a three-way compare but the specification says that it takes a three-way compare function and some (not all) implementations take advantage of the three possible cases. If your compare function doesn't conform to the specification, Undefined Behaviour will result. In this case, Undefined Behaviour might include a failure to sort correctly or a buffer overrun triggered on very rare corner cases, which you might not notice until the space shuttle is returning from orbit. So don't do that.

As to why an implementation might want the three-way comparison, here is one possibility: for inputs with a lot of repeated values, quicksort can be speeded up considerably by using a three-way partition. That can be done with a two-way comparison by doing the comparison twice in opposite directions, but an implementor, knowing that a three-way comparator is required, is likely to test for equality when that's what they want to know.

If element A == element B but the comparator function tells qsort that B > A then qsort will think there may be other elements which should be between A and B when that is not the case, and therefore perform unnecessary checks.

Technically, you can do with just less-than, because a == b is equivalent to !(a < b) && !(b < a).

If the quicksort inner loop is written equivalent to this:

while(x[i] < pivot) i++;  // less-than

while(pivot < x[j]) j--;  // less-than

then you can get away with only implementing <.

In any case, stick to the principle of least astonishment by making it more obvious what the caller is supposed to do -- if your compare function pointer is named compare and the function shouldn't behave like a usual stdlib qsort compare delegate, then it's a bad idea.

On the other hand, if your parameter is named something like less_than or isLessThan, it should be much more obvious to the caller what is expected from the comparison function:

 void sort(

     const void * arr,

     size_t num_items,

     size_t element_size, 

     bool (*is_less_than)(const void*, const void*)

 );