Why does qsort produce different output for same array but different ordering?-CodePudding

I am trying to sort an array in descending order with the help of qsort in C.

#include<stdio.h>
#include<stdlib.h>

int compareFloat(const void* p1, const void* p2){
    const float* pa = p1;
    const float* pb = p2;
    return pb - pa;
}

int main()
{
    float arr[] = {1.5, 1.6, 1.38};
    qsort(arr, 3, sizeof(float), compareFloat);
    printf("%.2f %.2f %.2f", arr[0], arr[1], arr[2]);
    return 0;
}

The output for above code is "1.60 1.38 1.50", which is wrong; but, when the array is initialized as float arr[] = {1.38, 1.6, 1.5}, the answer is correct (i.e. "1.6, 1.5, 1.38").

Why?

CodePudding user response：

In the comparison function

int compareFloat(const void* p1, const void* p2){
    const float* pa = p1;
    const float* pb = p2;
    return pb - pa;
}

you are returning a difference of two pointers. But you need to compare the pointed values instead of the pointers itself.

The function can look the following way

int compareFloat( const void* p1, const void* p2)
{
    float a = *( const float * )p1;
    float b = *( const float * )p2;

    return ( a < b ) - ( b < a );
}

Here is a demonstration program.

#include <stdio.h>
#include <stdlib.h>

int compareFloat( const void *p1, const void *p2 )
{
    float a = *( const float * )p1;
    float b = *( const float * )p2;

    return ( a < b ) - ( b < a );
}

int main( void )
{
    float arr[] = { 1.5, 1.6, 1.38 };
    const size_t N = sizeof( arr ) / sizeof( *arr );

    qsort( arr, N, sizeof( float ), compareFloat );

    printf( "%.2f %.2f %.2f\n", arr[0], arr[1], arr[2] );
}

The program output is

1.60 1.50 1.38

CodePudding user response：

The return value of your compareFloat function is wrong … for two reasons.

First, you are subtracting pointers, rather than the values they point to – so you would need *pb - *pa.

But, even then, your test will fail for values like 1.6 and 1.5, because the result of that subtraction will be non-zero but less than one. Thus, when converted to the int return type, the function will return 0 (signalling that the values are the same), even though they are not.

You need to return the result of at least two comparisons:

int compareFloat(const void* p1, const void* p2)
{
    const float* pa = p1;
    const float* pb = p2;
    return (*pa < *pb) - (*pa > *pb);
}

CodePudding user response：

Your comparison routine is incorrect.

return pb - pa;

Here you're subtracting the two pointer values.

If you were working with integers you would instead subtract the numbers the pointers point to:

return *pb - *pa;

But this won't work for floating point numbers due to truncation of the fractional part. You'll need to explicitly compare and return the proper value.

if (*pa > *pb) {
    return -1;
} else if (*pa < *pb) {
    return 1;
} else {
    return 0;
}

CodePudding user response：

Others have well pointed out 2 deficiencies:

OP's pointer subtraction should be a floating point FP subtraction/compare.

Result needs to be an int.

int compareFloat(const void* p1, const void* p2){
  const float* pa = p1;
  const float* pb = p2;
  // return pb - pa;
  return (*pb > *pa) - (*pb < *pa);
}

There is another issue: If either FP value may be a not-a-number NAN, additional concerns apply to keep the compare compliant. We need a sort that returns the opposite sign when the arguments are reversed. Also if a > b and b > c, then a > c. (*pb > *pa) - (*pb < *pa) above does not achieve that with NANs.

int compareFloat(const void* p1, const void* p2){
  const float f1 = *(const float *)p1;
  const float f2 = *(const float *)p2;
  if (isnan(f1)) {
    if (isnan(f2)) {
      // Since both are NA, just compare bit patterns
      return memcmp(p1, p2, sizeof (float));
    }
    return 1; // Consider NAN < all non-NANs
  }
  if (isnan(f2)) {
    return -1;
  }
  return (f2 > f1) - (f2 < f1);
}

int main() {
  float arr[] = {1.5f, 1.6f, NAN, 1.38f};  // Better to use float constants
  qsort(arr, 4, sizeof(float), compareFloat);
  printf("%.2f %.2f %.2f %.2f", arr[0], arr[1], arr[2], arr[3]);
  return 0;
}

Output

1.60 1.50 1.38 nan