Quicksorting floats, qsort question

I have this working code here, which sorts an array of floats. Both arrays are the same apart from the location of the decimal point. Apparently the qsort function works depending on the amount of decimals that the individual floats contain:

// Compilation: gcc qsort.c -g -lm -Wall -o qsort
// Usage: ./qsort

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

float changes[] = { 8.37, -9.197, -3.9662, 4.946, -3.6095, -2.534, 1.693, 2.1133, 2.3198, 8.21 };                    /* affected by compare */
//float changes[] = { 0.000837, -0.009197, -0.039662, 0.004946, -0.036095, -0.002534, 0.001693, 0.021133, 0.023198, 0.000821 };  /* unaffected by compare */
int  n = sizeof(changes)/sizeof(changes[0]);

int compare (const void * a, const void * b) { return ( *(float*)a - *(float*)b ); }

int main () {
  printf("Unsorted: ");
  for (int i = 0; i < n; i++) { printf("%.6f ", changes[i]); }
  printf("\n");

  qsort(changes, sizeof(changes)/sizeof(changes[0]), sizeof(float), compare);

  printf("Sorted:   ");
  for (int i = 0; i < n; i++) { printf("%.6f ", changes[i]); }
  printf("\n");

  return(0);
}

Output of first array is correct:

$ ./qsort 
Unsorted: 8.370000 -9.197000 -3.966200 4.946000 -3.609500 -2.534000 1.693000 2.113300 2.319800 8.210000 
Sorted:   -9.197000 -3.966200 -3.609500 -2.534000 1.693000 2.113300 2.319800 4.946000 8.370000 8.210000 

Output of second array is incorrect:

$ ./qsort 
Unsorted: 0.000837 -0.009197 -0.039662 0.004946 -0.036095 -0.002534 0.001693 0.021133 0.023198 0.000821 
Sorted:   0.000837 -0.009197 -0.039662 0.004946 -0.036095 -0.002534 0.001693 0.021133 0.023198 0.000821

What is this behaviour called? How do I correct it to work on the second sample-array?

a longhand modified version of your code (as you had commented the 2nd array out of the code)... , see if that does what you expect.

Re-read the qsort man page wrt the required behaviour of the comparison function. (i've embedded it in the below)

cat mysort.c
#include <stdio.h>
#include <stdlib.h>

float array1[] = { 8.37, -9.197, -3.9662, 4.946, -3.6095, -2.534, 1.693, 2.1133, 2.3198, 8.21 };                    /* affected by compare */
float array2[] = { 0.000837, -0.009197, -0.039662, 0.004946, -0.036095, -0.002534, 0.001693, 0.021133, 0.023198, 0.000821 };  /* unaffected by compare */
int  n = sizeof(array1)/sizeof(array1[0]);

int compare (const void * a, const void * b) 
{ 
	/*
	 * The comparison function must return an integer less than, equal to, 
	 * or greater than zero if the first argument is considered to be 
	 * respectively less than, equal to, or greater than the second. 
	 *
	 * If two members compare as equal, their order in the sorted array is undefined
	 *
	 */
	if ( *(float*)a > *(float*)b )
		return 1;
	if ( *(float*)a == *(float*)b )
		return 0;
	if ( *(float*)a < *(float*)b )
		return -1;
	
	
	/*
	return ( *(float*)a - *(float*)b ); 
	*/
}

int main () 
{
  printf("array1 UNSORTED: %ld array members, each %ld bytes ", sizeof(array1)/sizeof(array1[0]), sizeof(float));

  for (int i = 0; i < n; i++) 
	  printf("%.6f ", array1[i]); 
  printf("\n");

  qsort(array1, sizeof(array1)/sizeof(array1[0]), sizeof(float), compare);

  printf("array1   SORTED: %ld array members, each %ld bytes ", sizeof(array1)/sizeof(array1[0]), sizeof(float));
  for (int i = 0; i < n; i++) 
	  printf("%f ", array1[i]); 
  printf("\n\n\n");

  printf("array2 UNSORTED: %ld array members, each %ld bytes ", sizeof(array2)/sizeof(array2[0]), sizeof(float));

  for (int i = 0; i < n; i++) 
	  printf("%.6f ", array2[i]); 
  printf("\n");

  qsort(array2, sizeof(array2)/sizeof(array2[0]), sizeof(float), compare);

  printf("array1   SORTED: %ld array members, each %ld bytes ", sizeof(array2)/sizeof(array2[0]), sizeof(float));
  for (int i = 0; i < n; i++) 
	  printf("%f ", array2[i]); 
  printf("\n");
  return(0);
}

./mysort 
array1 UNSORTED: 10 array members, each 4 bytes 8.370000 -9.197000 -3.966200 4.946000 -3.609500 -2.534000 1.693000 2.113300 2.319800 8.210000 
array1   SORTED: 10 array members, each 4 bytes -9.197000 -3.966200 -3.609500 -2.534000 1.693000 2.113300 2.319800 4.946000 8.210000 8.370000 


array2 UNSORTED: 10 array members, each 4 bytes 0.000837 -0.009197 -0.039662 0.004946 -0.036095 -0.002534 0.001693 0.021133 0.023198 0.000821 
array1   SORTED: 10 array members, each 4 bytes -0.039662 -0.036095 -0.009197 -0.002534 0.000821 0.000837 0.001693 0.004946 0.021133 0.023198 

The result from compare is cast to an int. This is fine for keys that are ints, or for strings compared with strcmp(), because the result is only used as <0, ==0, >0.

However, casting small floats to int truncates them, which makes them look equal.

Your compare function needs to compare the results as floats, and return the corresponding int status. Something like:

float res = *(float*)a - *(float*)b
return ((res < 0.0) ? -1 : (res > 0.0) ? +1 : 0);

The output of your first array is in fact incorrect: e.g.

  ....  8.370000 8.210000

This is great, thank you for your efforts. Took the response from Paul_Pedant as the solution for it being terse.

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.