Why does the comparison function given to qsort() need to return three different values?

  • A+
Category:Languages

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: