Problem próbuje użyć funkcji C qsort

Question

#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; 
} 

Wynikiem jest:

-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

To źle ponieważ kolejność -1 i -1.1 zostało zmienione. Wierzę, że to się dzieje, ponieważ moja funkcja "porównaj".

Jak mogę rozwiązać ten problem?

Dzięki

Answer 1

przez zaokrąglenie różnicy do całkowitej utraty precyzji.

EDIT:

Zmienić funkcję porównania do

return (*(float*)a >= *(float*)b) ? 1 : -1;

Edit dla AndreyT: Nie sądzę, że powrót tylko 1 lub -1 spowoduje nieskończoną pętlę lub nieprawidłową kolejność (ja po prostu wymień równe wartości, które tego nie wymagają).

uwzględniając wyraźne argumenty za powrotem 0 będzie kosztować dodatkowe compatation pływaka, a są one rzadko równa. Zatem porównanie dla równości można pominąć, jeśli współczynnik kolizji w danych wejściowych jest mały.

Answer 2

Twoja funkcja porównania jest zepsuta. Mówi on na przykład, że -1.0 jest równe (równoważne) z -1.1, ponieważ (int) ((-1.0) - (-1.1)) jest równe zero. Innymi słowy, sam powiedziałeś qsort, że względna kolejność -1.0 i -1.1 nie ma znaczenia. Dlaczego jesteś zaskoczony, że w wynikowym porządku wartości te nie są sortowane?

Generalnie należy unikać porównywania wartości liczbowych poprzez odjęcie od siebie. To po prostu nie działa. W przypadku typów zmiennoprzecinkowych może powodować nieprecyzyjne wyniki z kilku różnych powodów, z których jeden właśnie zaobserwowałeś. Dla typów całkowitych może się przepełnić.

Ogólny idiom dla porównania dwóch wartości liczbowych a i b dla qsort wygląda jak (a > b) - (a < b). Zapamiętaj to i użyj go. W twoim przypadku to byłoby

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

w kodzie C może to uczynić sens zdefiniować makro

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

i używać go zamiast literowania porównań wyraźnie.