Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Problem trying to use the C qsort function

Tags:

c

c89

qsort

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

float values[] = { 4, 1, 10, 9, 2, 5, -1, -9, -2,10000,-0.05,-3,-1.1 };

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

int main ()
{

    int i;

    qsort (values, 13, sizeof(float), compare);

    for (i = 0; i < 13; i++)
    {
        printf ("%f ",values[ i ]);
    }
    putchar('\n');

    return 0;
}

The result is:

-9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.000000

It's wrong because the order of -1 and -1.1 is changed. I believe it is happening because my "compare" function.

How can I fix this?

Thanks

like image 785
Luiz Fernando Avatar asked Oct 07 '10 22:10

Luiz Fernando


People also ask

How does the qsort function work in C?

The qsort() function sorts an array of num elements, each of width bytes in size, where the first element of the array is pointed to by base. The compare pointer points to a function, which you supply, that compares two array elements and returns an integer value specifying their relationship.

What does qsort mean in C?

The qsort() is a C library function that uses a quick sort algorithm to sort an array. Here is how it is declared in C: A void pointer is a pointer that can point to any datatype. The most interesting part of the syntax above is the comparator function. It is called by qsort() , multiple times, to compare two elements.

Is qsort in C Stable?

Since quicksort is an unstable sort — there are multiple possible results when the array contains equivalent elements — this means qsort() is not guaranteed to be stable, even if internally the C library is using a stable sort like merge sort. The C standard library has no stable sort function.

What algorithm does qsort use?

As the name suggests, qsort function uses QuickSort algorithm to sort the given array, although the C standard does not require it to implement quicksort.


1 Answers

Your comparison function is broken. It says, for example, that -1.0 is equal (equivalent) to -1.1, since (int) ((-1.0) - (-1.1)) is zero. In other words, you yourself told qsort that the relative order of -1.0 and -1.1 does not matter. Why are you surprised that in the resultant ordering these values are not sorted?

In general, you should avoid comparing numerical values by subtracting one from another. It just doesn't work. For floating-point types it might produce imprecise results for quite a few different reasons, one of which you just observed yourself. For integer types it might overflow.

The generic idiom for comparing two numerical values a and b for qsort looks as (a > b) - (a < b). Remember it and use it. In your case that would be

int compare (const void * a, const void * b)
{
  float fa = *(const float*) a;
  float fb = *(const float*) b;
  return (fa > fb) - (fa < fb);
}

In C code it might make perfect sense to define a macro

#define COMPARE(a, b) (((a) > (b)) - ((a) < (b)))

and use it instead of spelling out the comparisons explicitly.

like image 76
AnT Avatar answered Sep 28 '22 00:09

AnT