Problem versucht, die C qsort Funktion

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

Das Ergebnis ist zu verwenden:

-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

Es ist falsch, weil die Reihenfolge von -1 und -1.1 wird geändert. Ich glaube, es passiert, weil meine "vergleichen" -Funktion.

Wie kann ich das beheben?

Dank

Answer 1

Durch den Unterschied zu dem ganzzahligen Rundungs ​​verlieren Sie die Präzision.

EDIT:

die Funktion vergleichen Ändern zu

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

Edit für AndreyT: Ich glaube nicht, dass nur 1 oder -1 Rückkehr wird eine Endlosschleife oder falsche Reihenfolge führen (es wird Tausche einfach gleiche Werte aus, die es nicht benötigt haben).

Ein expliziter Fall für die Rückgabe 0 kostet eine zusätzliche Float-Kompatibilität, und sie sind selten gleich. Somit könnte die Vergleichbarkeit für die Gleichheit weggelassen werden, wenn die Kollisionsrate in den Eingangsdaten klein ist.

Answer 2

Ihre Vergleichsfunktion ist kaputt. Es heißt zum Beispiel, dass -1.0 gleich (äquivalent) zu -1.1 ist, da (int) ((-1.0) - (-1.1)) Null ist. Mit anderen Worten, Sie selbst sagten qsort, dass die relative Reihenfolge von -1.0 und -1.1 keine Rolle spielt. Warum wundern Sie sich, dass in der resultierenden Reihenfolge diese Werte nicht sortiert sind?

Im Allgemeinen sollten Sie es vermeiden, numerische Werte durch Subtraktion von einander zu vergleichen. Es funktioniert einfach nicht. Bei Fließkommatypen kann es aus verschiedenen Gründen zu ungenauen Ergebnissen führen, von denen Sie gerade selbst beobachtet haben. Bei Integer-Typen kann es zu einem Überlauf kommen.

Das allgemeine Idiom zum Vergleichen zweier Zahlenwerte a und b für qsort sieht wie (a > b) - (a < b) aus. Erinnere dich daran und benutze es. In Ihrem Fall, dass

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 wäre es durchaus Sinn machen könnte ein Makro

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

und es verwenden, statt formulierend die Vergleiche explizit zu definieren.