Проблема при попытке использовать функцию C qsort - PullRequest
Новая
       7

Проблема при попытке использовать функцию C qsort

11 голосов
/ 08 октября 2010 
#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 изменено.Я полагаю, что это происходит из-за моей функции сравнения.

Как я могу это исправить?

Спасибо

Ответы [ 3 ]

36 голосов
/ 08 октября 2010

Ваша функция сравнения не работает.Он говорит, например, что -1.0 равно (эквивалентно) -1.1, поскольку (int) ((-1.0) - (-1.1)) равно нулю.Другими словами, вы сами сказали qsort, что относительный порядок -1.0 и -1.1 не имеет значения.Почему вы удивляетесь, что в результирующем порядке эти значения не сортируются?

В общем, вам следует избегать сравнения числовых значений путем вычитания одного из другого.Это просто не работает.Для типов с плавающей запятой это может привести к неточным результатам по нескольким причинам, одна из которых вы только что наблюдали сами.Для целочисленных типов он может быть переполнен.

Общая идиома для сравнения двух числовых значений 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);
}

. В коде на С может иметь смысл определить макрос 

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

и использовать его вместо того, чтобы явно описывать сравнения.

1 голос
/ 08 октября 2010

Округляя разницу до целого, вы теряете точность.

РЕДАКТИРОВАТЬ:

Изменить функцию сравнения на

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

Редактировать для AndreyT: я не думаю, что возвращение только 1 или -1 вызовет бесконечный цикл или неправильный порядок (он будет просто обмениваться равными значениями, которые ему не нужны).

Наличие явного случая для возврата 0 обойдется дополнительным числом с плавающей запятой, и они редко равны. Таким образом, сравнение равенства может быть опущено, если частота столкновений во входных данных мала.

0 голосов
/ 26 апреля 2018

Чтобы добавить к существующему ответу @AnT, вы можете автоматически подтвердить свой qsort обратный вызов через SortChecker : 

$ 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 < z, а не x < z для некоторых входов. Для дальнейшей отладки этой проблемы запустите с 

export SORTCHECK_OPTIONS=raise=1

и изучите сгенерированный codedump.

...