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

結果は次のとおりです。

-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

-1と-1.1の順番が入れ替わっているので間違っています。私の「比較」機能が原因で起こっていると思います。

どうすればこれを修正できますか?

ありがとう

4

3 に答える 3

40

比較機能が壊れています。たとえば、はゼロなので、-1.0はと等しい（同等）と言います。言い換えれば、あなた自身が、との相対的な順序は重要ではないと言ったのです。結果の順序でこれらの値が並べ替えられないことに驚いたのはなぜですか？-1.1(int) ((-1.0) - (-1.1))qsort-1.0-1.1

一般に、数値を減算して数値を比較することは避けてください。それはうまくいきません。浮動小数点型の場合、かなりの数の異なる理由で不正確な結果が生成される可能性がありますが、そのうちの1つは自分で観察したものです。整数型の場合、オーバーフローする可能性があります。

2つの数値を比較し、のように見える一般a的bなqsortイディオム(a > b) - (a < b)。それを覚えて使用してください。あなたの場合、それは

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

Cコードでは、マクロを定義するのが完全に理にかなっているかもしれません

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

比較を明示的に綴る代わりにそれを使用します。

于 2010-10-07T22:56:47.173 に答える
1

差を整数に丸めると、精度が失われます。

編集：

比較関数を次のように変更します。

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

AndreyT の編集: のみを返すか、無限ループまたは不適切な順序が発生するとは思わない1(-1それを必要としない等しい値を交換するだけです)。

返すための明示的なケースが0あると、追加の浮動小数の計算が必要になり、それらが等しくなることはめったにありません。そのため、入力データの衝突率が小さい場合は、等値の比較を省略できます。

于 2010-10-07T22:51:17.013 に答える
0

@AnT による既存の回答に追加するには、SortChecker を介してコールバックを自動的に検証できqsortます。

$ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out
a.out[7133]: qsort: comparison function is not transitive (comparison function 0x4005cd (/home/iuriig/a.out+0x4005cd), called from 0x400614 (/home/iuriig/a.out+0x400614), cmdline is "./a.out")
-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

この警告は、一部の入力に対してではなく、compareレポートであることを示しています。この問題をさらにデバッグするには、次のように実行しますx < y, y < zx < z

export SORTCHECK_OPTIONS=raise=1

生成されたコードダンプを調べます。

于 2018-04-26T09:03:03.600 に答える